정렬 알고리즘 - 힙 정렬
힙 정렬(Heap Sort)
- 힙 정렬은 비교 기반 정렬 알고리즘이다.
- 선택 정렬 알고리즘과 비슷하게 정렬 된 영역과 아닌 영역을 나누어 가장 큰 요소를 찾아 정렬된 영역으로 배치시킨다.(오름차순 기준)
- 선택 정렬 보다 개선된 점은 선형 시간이 소요되는 선택 정렬의 탐색과 달리 힙 자료구조를 사용하여 최댓값을 탐색한다.
- 선택 정렬 시간 복잡도 : O(N^2)
- 힙 정렬 시간 복잡도 : O(nlog(n))
시간복잡도
- 최선의 경우 : O(nlog(n))
- 최악의 경우 : O(nlog(n))
장점
- 최악의 경우에도 O(nlog(n)) 의 빠른 속도가 보장된다.
- 추가적인 메모리를 필요로 하지 않는다.
단점
- 정렬간의 데이터 안정성을 보장받지 못한다. 즉, 중복의 데이터의 경우 순서가 바뀌는 unstable한 알고리즘
- 데이터의 상태에 따라 다른 정렬법 보다 느릴 수 있다.
구현
function HeapSort(arr) {
for (let i = parseInt(arr.length / 2); i >= 0; i--) {
Heapify(arr, i);
}
for (let i = arr.length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
Heapify(arr, 0, i);
}
return arr;
}
function Heapify(arr, idx, length = arr.length) {
let leftIdx = idx * 2 + 1;
let rightIdx = idx * 2 + 2;
let max = idx;
if (leftIdx < length && arr[leftIdx] > arr[max]) {
max = leftIdx;
}
if (rightIdx < length && arr[rightIdx] > arr[max]) {
max = rightIdx;
}
if (max !== idx) {
[arr[idx], arr[max]] = [arr[max], arr[idx]];
Heapify(arr, max, length);
}
return arr;
}
console.log(HeapSort([6, 5, 3, 1, 8, 7, 2, 4]));
Author And Source
이 문제에 관하여(정렬 알고리즘 - 힙 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@codenmh0822/정렬-알고리즘-힙-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)