힙 정렬(heap sort) 구현하기(c++)

힙 정렬은 개인적으로 heap구조를 구현해야하기 때문에 어려운? 알고리즘 중 하나라고 생각한다.

혼자서 짜보려고 노력해봤지만.. 한계를 느껴 다른 분의 해설을 보고 구현해보았다.

나는 주어진 배열을 힙의 형태로 만들어주는 방식으로 정렬을 했다.

 

 

*핵심 포인트*

1) 주어진 배열을 위->아래 순으로 자식이 부모보다 큰 경우를 처리해준다.

2) 아래->위로 각 배열의 원소들을 루트 노드로 올려 자식들 중 큰 값이랑 교한해주는 힙 구조로 정렬을 해나갔다.

 

 

*시간 복잡도*

Best	Avg	Worst
O(nlog(n))	O(nlog(n))	O(nlog(n))

 

 

코드 첨부

// 힙 정렬 구현(오름차순)
/*
    힙 정렬은 2가지 구현방식이 존재한다.
    1) 데이터들을 힙에 넣었다가 꺼내는 원리로 정렬하는 것
    2) 기존의 배열을 heap으로 만들어주는 과정을 거쳐 꺼내주는 방법
*/
 
#include <iostream>
using namespace std;
 
int arr[8] = {7, 6, 2, 8, 3, 5, 4, 1};
 
int main()
{   
    // 기존의 arr배열을 자식이 부모보다 큰 경우를 1차 정렬해준다.
    // 아래 -> 위
    for(int i=1; i<8; i++){
        int c = i;
        do{
            int root = (c-1)/2;
            if(arr[root]<arr[c]){
                int temp = arr[root];
                arr[root] = arr[c];
                arr[c] = temp;
            }
            c = root;
        }while(c!=0);
    }
 
    // 위 -> 아래
    for(int i=7; i>=0; i--){
        // i번째 원소를 0번(root node)으로 올려주고 heap구조로 재배치한다.
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        int root = 0;
        int c = 1;
 
        do{
            c = (2*root)+1; // 왼쪽 자식
            // c<i-1인 이유는, 왼쪽 자식이기 때문에 1칸 더 여유가 있어야 한다.
            if(c<i-1 && arr[c]<arr[c+1]){ // 왼쪽자식<오른쪽 자식
                c++;
            }
 
            // 왼쪽 자식과 오른쪽 자식 중 더 큰 값(c)과 바꾼다. 
            if(c<i && arr[root]<arr[c]){
                temp = arr[root];
                arr[root] = arr[c];
                arr[c] = temp; 
            }
            root = c;
        }while(c<i);
    }
 
    for(int i=0; i<8; i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
 
    return 0;
}
 

 

 

위 표는 아래 블로그를 참조했습니다.

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog