힙 정렬 (Heap Sort)
힙 정렬은 기본적으로 힙 자료구조를 기반으로 한 정렬 방식이다.
힙 정렬은 불안정 정렬에 속하며, 다음과 같은 과정을 거친다.
1.
최대 힙을 구성
2.
현재 힙 루트는 가장 큰 값이 존재함, 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄인다.
3.
힙의 사이즈가 1보다 크면, 위 과정 반복한다.
시간복잡도
최악, 최선, 평균 모두 NlogN 의 시간복잡도를 가진다.
장점
•
성능이 좋다.
•
부가적인 메모리가 필요없다.
•
어떠한 입력 데이터에 대해서도 최대복잡도 O(NlogN)을 보장
단점
•
실제 프로그램에서 실행할 경우, 평균적인 계산 속도에서 퀵 정렬보다 늦고 안정되지 못함
힙 소트가 유용할 때
•
가장 크거나 가장 작은 값을 구할 때
◦
최소 힙 or 최대 힙의 루트 값이기 때문에, 한번의 힙 구성을 통해 구하는 것이 가능하다
•
최대 k만큼 떨어진 요소들을 정렬할 때
◦
삽입 정렬보다 더욱 개선된 결과를 얻어낼 수 있음
소스코드
#include <iostream>
using namespace std;
int n;
int heap[100000001];
void heapify(int i) {
int cur = 2 * i;
if (cur < n && heap[cur] < heap[cur+1]) cur++;
if (heap[i] < heap[cur]) {
swap(heap[i], heap[cur]);
if (cur <= n/2) {
heapify(cur);
}
}
}
void heapsort(int i) {
swap(heap[1], heap[i]);
int root = 1;
int cur = 2;
while (cur/2 < i) {
cur = 2 * root;
if (cur < i-1 && heap[cur] < heap[cur+1]) cur++;
if (cur < i && heap[root] < heap[cur]) {
swap(heap[root], heap[cur]);
}
root = cur;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> heap[i];
}
for (int i = n/2; i > 0; i--) { // 최초 heap 생성
heapify(i);
}
for (int i = n; i > 0; i--) { // 힙 정렬
heapsort(i);
}
for (int j = 1; j <= n; j++) { // 출력
cout << heap[j];
}
}
C++
복사