[C] 힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

---

힙(Heap) ?  

최대값, 최소값을 찾아내는 연산을 빠르게 하기위해 고안된 완전트리를 기본으로 한 자료구조

힙정렬

힙 정렬은 분할정복 알고리즘으로 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 입니다.

어떠한 방법?

예제는 배열을 이용해서 트리구조를 구성했습니다.

배열을 이용한 트리구조에서 주의할 점은 균형 잡히지 않은 노드의 경우 실제로 없는 노드를 위해 배열 공간을 확보해야 하기 때문에 균형잡힌 노드에 한해서 사용 가능합니다.

---

아래와 같은 이진트리가 있을 때

A노드부터 1번부터 12번까지 숫자를 매기면 아래 그림과 같습니다.

이 때 i노드의 부모번호는 i/2

i노드의 왼쪽 자식노드는 2i 오른쪽 자식노드는 2i+1을 만족합니다.

예) 5번 노드의 부모노드 번호는 5/2=2(버림)

4번 노드의 왼쪽 자식노드는 4*2=8 오른쪽 자식도느는 4*2+1 = 9

이 개념을 이용하면 배열을 이용해서 트리를 구성할 수 있습니다.

---

배열을 이용한 힙 정렬 예제

upHeap함수

아래에서 위로 올라가면서 자리를 바꾸는 함수입니다.

void upHeap(int array[], int k){

int v;

v = array[k];

array[0] = MAX;

while (array[k/2]<=v) // 부모 <= 자식

{

array[k] = array[k/2];

k/=2;

}

array[k] = v;

}

downHeap함수

upHeap함수와 반대로 아래로 내려가면서 비교하는 함수입니다.

자식노드 왼쪽과 오른쪽 노드를 비교해서 더 큰 노드를 이용합니다.

void downHeap(int array[], int n, int k){

int i;

int v = array[k];

while(k<=n/2){

i = k<<1; // 2*k

if(i<n && array[i]<array[i+1]) i++; //왼쪽, 오른쪽 노드 비교

if(v>=array[i]) break;

array[k] = array[i];

k=i;

}

array[k] = v;

}

insert, delete함수

insert는 입력받은 배열을 트리구조로 사용하기 위해 입력하는 함수

delete는 정렬된 데이터를 받아오는 함수 입니다.

void insert(int array[], int *hn, int v){

array[++(*hn)] = v;

upHeap(array, *hn);

}

int delete(int array[], int *n){

int v = array[1];

array[1] = array[(*n)--];

downHeap(array, *n, 1);

return v;

}

힙 정렬 함수

입력받은 배열을 정렬하는 함수입니다.

첫번 째 for문 : 배열을 순차적으로 삽입

두번 째 for문 : 정렬된 데이터를 꺼냄

마지막 for문 : 정렬시에 0번째에는 큰 수를 넣어놓고

1번째 인덱스부터 이용했기 때문에 

한칸씩 당겨주는 for문

void heap_sort(int array[], int n){

int hn = 0;

int i= 0;

for(i=1; i<=n; i++)

insert(array, &hn, array[i]);

for(i=hn; i>=1; i--){

array[i] = delete(array, &hn);

}

for(int j=0; j<n; j++){

array[j] = array[j+1];

}

}

배열 출력 함수

void print_array(int array[], int size){

for(int i=0; i<size; i++){

printf("%-4d",array[i]);

}

printf("\n");

}

메인 함수

정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.

정렬을 하고나면 배열의 크기가 변하기 때문에

oldSize변수에 초기 크기를 저장해두고 진행했습니다.

void main(){

int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};

int oldSize = sizeof(array)/sizeof(int);

int size = sizeof(array)/sizeof(int);

printf("########### Sorting before ###########\n");

print_array(array, size);

heap_sort(array, size);

printf("########### Sorting after ###########\n");

print_array(array, oldSize);

}

실행 결과

---

참고 : C로 배우는 알고리즘 (이재규)

  위키백과(힙 ,힙 정렬)

---

관련 포스팅

[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)