힙 정렬(Heap Sort)

힙 정렬(Heap-Sort)

- 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬하는 방식

- 일반적으로 O( n log n)의 복잡도를 가진다.

( 퀵 정렬은 최악의 경우 O(n²)의 복잡도를 가지기 때문에 힙 정렬이 선호된다.)

동작 원리

1. 최대(최소) 힙을 구성한다. 자노드를 가진 부노드부터 구성하며, 아래부터 루트까지 순차적으로 구성한다.

2. 루트에 위치한 수와 가장 작은 수를 교환한다.

3. 교환한 수를 제외하고 힙의 특성을 유지시킨다.

4. 위의 2와 3 과정을 반복한다.

함수 설명

- heap_sort() : 동작 원리 "2"의 과정을 수행하는 함수

- build_max_heap() : 동작 원리 "1"의 과정을 수행하는 함수로 기본적인 힙의 구조를 구성한다.

- max_heapify() : 최대 힙의 특성을 유지시켜주는 기능을 수행, 동작 원리 "3"에 해당한다.

 

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

#define MAX  10 // size of array

void display_elements( int *, int);
void heap_sort( int *, int);
void max_heapify( int *, int, int);
void build_max_heap( int *, int);

int main( void)
{
 int arry[MAX]  = { 0,};
 int count   = 0;
 int size   = 0;

 srand( time(NULL)); // used to init random

 size  = sizeof(arry)/4;

 // init elements of array with random numbers
 for( count = 0 ; count < size ; count ++)
 {
  arry[count]  = rand()%(MAX*10);
 }

 // display elements of array
 printf("Before sorting : ");
 display_elements( arry, size);

 // call Heap-Sort
 heap_sort( arry, size);

 // output result
 printf("\n After sorting : ");
 display_elements( arry, size);

 return 0;
}

void display_elements( int *ar, int s)
{
 int count  = 0;

 for( count = 0 ; count < s ; count ++)
 {
  printf("%4d", ar[count]);
 }
}

void heap_sort( int *ar, int size)
{
 int count = 0;
 int temp = 0;

 build_max_heap( ar, size);

 for( count = size-1 ; count > 0 ; count--)
 {
  // exchange root with the smallest element
  temp  = ar[count];
  ar[count] = ar[0];
  ar[0]  = temp;

  // maintain heap-structure
  max_heapify( ar, count, 0);
 }
}

void build_max_heap( int *A, int s)
{
 int i  = 0;

 /*
  build max-heap structure
 */
 for( i = (s/2)-1 ; i >= 0 ; i --)
 {
  max_heapify( A, s, i);
 }
}

void max_heapify( int *A, int size, int index)
{
 int left = index * 2;
 int right = index * 2 + 1;
 int largest = index;
 int temp = 0;

 // check the element on the left to find the largest element
 if( left < size && A[left] > A[index])
 {
  largest = left;
 }

 // check the element on the right to find the largest element
 if( right < size && A[right] > A[largest])
 {
  largest = right;
 }

 // finding the element larger than index, exchange index with largest
 if( largest != index)
 {
  temp  = A[largest];
  A[largest] = A[index];
  A[index] = temp;

  // recursion to maintain heap-structure
  max_heapify( A, size, largest);
 }
}