Develop Develop

거품, 힙 중에서 가장 빠른 알고리즘이다. 분할정복이라는 접근 방식을 이용해서 배열을 정렬하는 재귀적인 알고리즘이다. 1. 기준값 하나 선택 2. 그 기준값보다 작은 항목들을 배열의 왼쪽으로 3. 그 기준값보다 큰 항목들을 배열의 오른쪽으로 4. 왼쪽 부분 배열에 퀵 정렬을 재귀적으로 적용 5. 오른쪽 부분 배열에 퀵 정렬을 재귀적으로 적용 퀵정렬이 가장 효율적으로 작동하려면 두 부분배열들의 크기가 거의 비슷해야한다. 삼중앙 알고리즘을 쓰는데 첫 번째 중간 마지막 색인의 값들을 취해서 그 셋 중 가운데 값을 기준값으로 사용 11 10 16 4 8 12 1 6 0 20 2 9 5 이렇게 있을때 제일앞의 11 중간의 1 마지막의 5를 취하고 그중 가운데에 해당하는 5를 기준값으로 선정 기준값을 밖으로 뺀다 ..

힙은 우선순위 대기열에 사용하기에 매우 효율적일 뿐만 아니라 효율적인 정렬 알고리즘으로도 쓰일 수 있다. 힙에서 흥미로운 점은 힙 자체에 정렬 기능을 가지고 있다. 힙의 특성은 항상 부모 노드가 자식 노드들보다 큰 값을 가진다는 것 이것을 정렬에 활용할 수 있다. 간단히 말해서 배열의 항목들을 모두 힙에 넣은 다음 한 번에 하나씩 힙에서 가장 큰 값을 뽑아 다시 배열에 저장하면 정렬된 배열이 만들어지는 것이다. 힙의 삽입 삭제 알고리즘 모두 O(log2n)이므로 효율도 좋다 그러나 단점이 있다. 필요한 공간이 두배로 늘어난다. 대량의 자료를 정렬한다면 문제가 된다. (옮겨야 하니까..뽑아서 옮기고 뽑아서 옮기고..) 공간 문제를 해결할 방법은 없는가? 무작위적인 자료가 담긴 배열을 힙으로 변환할 수 있다..

현존하는 정렬 알고리즘들 중에서 가장 느리다.이것은 일종의 잘 될 때까지 "무작정" 시도하는 알고리즘이라고 할 수 있다.마치 거품이 물 위로 떠오르는 것처럼 정렬이 된다고 해서 거품정렬..(오른차순으로 정렬을 할 경우) * 거품 정렬의 최악의 경우 오른차순 정렬인데 내림차순으로 되어 있는 경우.. 본질적으로 이중for루프 사용하고 정렬 알고리즘은 n^2에 속한다. 거품 정렬의 최적화2가지 염두해야할 사항이 있다.1. 함수가 하나의 반복에서 색인들을 한 번도 바꾸지 않았다면 이미 정렬된것이다.2. 알고리즘이 ?번 반복되었다면 상위 ?개의 색인들은 이미 정렬된 상태이다. 알고리즘 의사코드Bubblesort(Array)int swaps=1int top=Array.size-1;int indexwhile(top!..

등고선 알고리즘이란? 길찾기 알고리즘의 한 종류로 도착점에 0이라는 숫자를 넣고 주변을 검사하여 벽이 아닌 인접한 블록에 1로 쓴다. 다시 1 주변을 검사하여 벽이 아닌 인접한 블록에 2를 쓰고,이런 식으로 출발점까지 가장 적은 수가 나오는 경로를 찾아가는 알고리즘이다. 이러한 방법이 마치 등고선을 그리는 방법과 비슷하여 등고선법이라고 한다. 구현방법 1. 각 셀을 -1로 초기화 한다. -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2. 도착점을 0으로 설정한다. -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 3. 도착점부터 각 셀에 순서대로 번호를 매긴다. -1 -1 4 -1 -1 3 -1 4 3 2 -1 -1 1 ..