정렬 알고리즘(힙 정렬)

ggh·2022년 5월 11일
Sortalgorithmcpp
0

algorithm

목록 보기
4/13

힙 정렬 (Heap Sort)

개yo

이번 포스팅에선 힙 정렬 (Heap Sort)에 대해 알아볼 것이다. 힙 정렬은 이전 포스트에서 다뤘던 퀵 , 병합 정렬 과 마찬가지로 시간복잡도가 O(N *log N) 인 빠른 정렬 알고리즘이다. 힙 정렬을 이해하기 위해선 이진트리, 힙을 이해해야 하기에 이번 포스트에서 함께 알아볼 것이다.

문제

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

SOL

문제를 해결하기 위해 “힙(Heap)을 이용하여 데이터를 정렬하기”를 생각해 볼 수 있다.

이를 이용한 방법을 힙 정렬 이라고 부른다. 힙정렬은 힙 트리 구조로 이루어저 있어 각각 힙, 트리가 무엇인지 알아야 한다.

완전 이진 트리(Complete Binary Tree)

아래와 같은 구조를 이진 트리라고 한다. 말 그대로 2개의 트리 모양인데 줄기와 가지를 생각하면 된다. 따라서 위 구조는 하나의 줄기에 2개의 가지를 가진 상태다.

1

특징

  • 노드 (1) : 노드(2) (3)의 부모노드
    • 루트(Root) 노드
  • 노드(2) (3) : 노드 (1)의 자식노드
  • 노드(4) (5), 노드(6) : 노드(2) (3)의 자식 노드
    • 리프(Leaf) 노드

좀 더 자세하게 말하자면 위 구조는 이진트리 중에서도 완전 이진트리다.

완전 이진 트리는 위와 같이 6개의 데이터가 존재 할때 루트 노드를 시작으로 왼쪽부터 빈 노드없이 채워지는 트리를 말한다.

힙(Heap)

완전 이진 트리에 대해 알아보았으니 이제 힙(Heap)에 대해 알아보도록 하겠다.

힙은 완전이진 트리를 사용하여 최대, 최소힙으로 두가지로 나눠지고 이는 최솟값이나 최댓값을 빠르게 찾아내기 위해 쓰인다.

힙

특징

위와 같은 구조를 힙이라고 하며, 힙 중에서도 최대 힙이다.

  • 최대힙은 부모 노드의 값이 자식 노드의 값보다 커야한다.

두번째 예제처럼 최대힙이 붕괴되는 경우에는 자식 노드와 부모 노드를 바꿔야 한다.

  • swap(자식 노드(7), 부모 노드(5))

위와 같은 경우를 힙생성 알고리즘이라고 한다.

만약 바꾼 뒤에도 붕괴되는 경우라면 아랫단의 자식과 바꿔야 한다.

  • 언제까지??? 붕괴되는 경우가 일어나지 않을 때 까지

위와 같은 힙 생성 알고리즘은 전체 트리의 힙 구조를 가진다. 또한 트리를 보면 알 수 있듯이 자식 노드로 내려갈수록 노드의 개수가 2배씩 증가한다. 이러한 특징은 시간복잡도의 측면에서 봤을 때 O(log N)이 수행된다.

문제

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

[ 7 6 5 8 3 5 9 1 6 ]

구현

  1. 힙을 구성한다.
  2. 크기를 줄여가며 반복적으로 힙을 구성한다.
  3. 자식 중에 더 큰 값을 찾는다.
  4. 루트보다 자식이 크면 교환한다. 
#include<iostream>

using namespace std; 

int num = 9;
int heap[9] = {7,6,5,8,3,5,9,1,6}; // 완전 이진 트리 구조 

int main()
{   
    cout << "정렬 전 : ";
    for(auto el : heap)
        cout << el << " ";
    cout << endl;
    // 전체 트리 구조를 최대 힙 구조로 바꾼다.  
    for(int i=1; i < num; i++)
    {
        int c = i; // 자식노드 
        do 
        {
            int root = (c-1) / 2; // 0 index 1회 실행  
            if(heap[root] < heap[c]) // 0 1 
                swap(heap[root], heap[c]);
            c = root; // index init 1 ~> 0 
        }
        while(c != 0); // c는 0이 되기 때문에 1회만 실행하고 꺼짐 
    }
    cout << "힙 구성 : ";
    for(auto el : heap)
        cout << el << " ";
    cout << endl;

    // 크기를 줄여가며 반복적으로 힙을 구성한다.
    // root노드의 요소 값을 맨 뒤 리프노드와 바꾼다.   
    for(int i = num-1; i >= 0; i--)
    {   
        // root 노드와 맨 뒤 leaf노드 스왑 
        swap(heap[0], heap[i]);
        int root = 0; //root 노드 
        int c = 1; // n 번째 자식노드 
        do
        {
            c = 2 * root + 1; // 자식노드 1
            // 자식 노드 중 더 큰 값을 찾는다. 왼 오 비교 
            // 언제까지? 마지막 leaf노드까지~   
            if(c < i-1 && heap[c] < heap[c + 1])
                c++; // 2 
            // root 노드보다 자식 노드가 크면 스왑 
            if(c < i && heap[root] < heap[c])
                swap(heap[root], heap[c]);
            // 재귀적 구조 
            root = c; // 0으로 초기화   
        }
        while(c < i);
    }
    cout << "힙 정렬 : ";
    for(auto el : heap)
        cout << el << " ";
    cout << endl;

}

출력

정렬 전 : 7 6 5 8 3 5 9 1 6 
힙 구성 : 9 7 8 6 3 5 5 1 6 
힙 정렬 : 1 3 5 5 6 6 7 8 9

해설

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

  1. 힙 구조 구현 

    for(int i=1; i < num; i++)
    {
        int c = i; // 자식노드 
        do 
        {
            int root = (c-1) / 2; // 0 index 1회 실행  
            if(heap[root] < heap[c]) // 0 1 
                swap(heap[root], heap[c]);
            c = root; // index init 1 ~> 0 
        }
        while(c != 0); // c는 0이 되기에 1회만 실행하고 꺼짐 
    }

  2. 자식 중에 루트보다 더 큰 값을 찾는다.

  3. 루트보다 자식이 크면 교환한다. 

    for(int i = num-1; i >= 0; i--)
    {   
        // root 노드와 맨 뒤 leaf노드 스왑 
        swap(heap[0], heap[i]);
        int root = 0; //root 노드 
        int c = 1; // n 번째 자식노드 
        do
        {
            c = 2 * root + 1; // 자식노드 1
            // 자식 노드 중 더 큰 값을 찾는다. 왼 오 비교 
            // 언제까지? 마지막 leaf노드까지~   
            if(c < i-1 && heap[c] < heap[c + 1])
                c++; // 2 
            // root 노드보다 자식 노드가 크면 스왑 
            if(c < i && heap[root] < heap[c])
                swap(heap[root], heap[c]);
            // 재귀적 구조 
            root = c; // 0으로 초기화   
        }
        while(c < i);
    }

마무리

  • 힙 정렬은 이전에 다뤘던 병합정렬과 다르게 별도의 추가적인 배열이 필요없어 공간 복잡도 측병에서 효율적이다.
  • 시간복잡도가 항상 O(N * log N)을 보장한다.
    • 이론적으로 퀸, 병합 정렬보다 더 효율성이 좋다.
      • 허나 평균 속도를 보자면 퀵 정렬이 더욱 빠르기에 잘 사용하지 않는다.
  • 루프 내의 코드가 길고, 비효율적인 개시메모리 사용을 하기에 따라 특히 대용량의 데이터를 정렬하기엔 부적절하다.

추가 문제

입력

[ 7 ]

[ 3 1 4 1 5 9 2 ]

힙 정렬의 과정을 출력하는 코드를 작성하여라.

  • 단 하향식 힙 정렬을 사용하여라

구현

#include<iostream>
#include<vector>

using namespace std; 

// 힙 구조 만들기 
// 자식 노드와 비교 후 스왑 
// 단 자식 노드에서만 
int num = 10;
int heap[] = {26,5,37,1,61,11,59,15,48,19};

void heapify(int i)
{
    // 왼쪽 자식노드 
    int c = 2 *i + 1;
    // 오른쪽 자식노드가 있고 왼쪽 자식노드보다 크면 
    if(c < num && heap[c] < heap[c+1])
        c++;
    // 부모 노드보다 자식노드가 크면 스왑
    if(heap[i] < heap[c])
        swap(heap[i], heap[c]);
    // num / 2 까지만 왜? why?
    // 실질적으로 봐야되는 데이터는 절반으로 나누기 때문  
    if(c <= num / 2) heapify(c);
}

int main()
{
    // 힙 구조 생성 
    for(int i=num/2; i >= 0; i--)
        heapify(i);
    // 힙 정렬
    for(int i=num; i >=0; i--)
    {
        cout << "정렬중 ";
        for(int j=0; j < num; j++)
        {
            cout << heap[j] << " ";
        }
        cout << '\n';
        swap(heap[0], heap[i]);
        int root = 0;
        int c = 1; 
        do
        {
            c = 2 * root + 1; // index 1부터 
						// 범위안에 해당되고 오른쪽 값보다 작으면 
            if(c < i-1 && heap[c] < heap[c + 1]) c++;
						// 하향식으로 스왑
            if(c < i && heap[root] < heap[c])
                swap(heap[root], heap[c]);
            root = c;
        } 
        while(c < i);  
    } 
}

Reference

10. 힙 정렬(Heap Sort)

profile
ggh
See you in a minute. : )
이전 포스트

정렬 알고리즘(버블 정렬)

다음 포스트

정렬 알고리즘(퀵 정렬)

0개의 댓글