[c++] 알고리즘 - 히프 정렬

히프 정렬 (Heap Sort)

히프(heap)를 이용해 정렬 (히프 : 우선순위 큐의 일종)

- 정렬할 원소를 모두 공백 히프에 하나씩 삽입

- 한 원소씩 삭제 →제일 큰 원소가 삭제됨

- 이 원소를 리스트의 뒤에서부터 차례로 삽입

- 오름차순으로 정렬된 리스트를 생성

히프 구성 방법

- 상향식(bottom-up) : 정렬할 배열을 완전 이진 트리라고 간주하고, 인덱스가 N/2인 노드부터 차례대로 인덱스를 감소시키면서 히프 구조로 변환

- 하향식(top-down) : 공백 히프에 차례대로 한 원소씩 삽입하여 히프를 구성

 

 

 

 

 

 

상향식 히프 구성

 

 

 

 

 

 

 

 

 

수행 과정

 

 

 

 

 

 

 

 

 

 

 

성능 특성

- 제자리 정렬이지만 불안정적

- N 개의 원소를 정렬하는데 N logN 단계가 필요함

- 입력 배열의 순서에 민감하지 않음

- 내부 루프가 퀵 정렬보다 약간 길어서 평균적으로 퀵 정렬보다 2배 정도 느림

 

 

 

 

 

 

소스 코드

#include <iostream>
#include <time.h>
#include <stdlib.h>

#define N 10
int a[N+1];//= { -1, 6, 2, 8, 1, 3, 9, 4, 5, 10, 7 };

using namespace std;

const int TRUE = 1;
const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
 int t = a[i]; a[i] = a[j]; a[j] = t;
}
void printList(int a[], int n)
{
 int i;
 for (i = 1; i < n; i++)
  cout << a[i] << ", ";
 cout << a[i] << endl;
}
void CheckTime(int a[], int n)
{
 int i, Sorted;
 Sorted = TRUE;
 for (i = 1; i < n; i++) {
  if (a[i] > a[i+1]) Sorted = FALSE;
  if (!Sorted) break;
 }
 if (Sorted) cout << "정렬 완료." << endl;
 else cout << "정렬 오류 발생." << endl;
}

void heapify(int a[], int h, int m)
{
 int j, v;
 v = a[h];
 for (j = 2*h; j <= m; j *= 2) {
  if (j < m && a[j] < a[j+1]) j++;
  if (v >= a[j]) break;
  else a[j/2] = a[j];
 }
 a[j/2] = v;
}

void HeapSort(int a[], int n) {
 int i;
 for ( i = n/2; i >= 1; i-- )
  heapify(a, i, n);

 for ( i = n-1; i >= 1; i-- ) {
  swap(a, 1, i+1);
  heapify(a, 1, i);

 }
}

void main()
{
 //int i;
 //double start_time;

 //srand(time(NULL));
 //for (i = 1; i <= N; i++) a[i] = rand();

 //start_time = clock();
 HeapSort(a, N);
 //cout << "히프 정렬의 실행 시간 (N = " << N << ") : " <<
  clock() - start_time << endl;
 //CheckTime(a, N);
}