[56회 변리사 2차-3번] Heap Sort

2019년 제 56회 변리사 2차 데이터 구조론 2교시 3번 문제 해설

​

 

Heap Sort  (힙 정렬)

힙정렬을 하기 위해서는 데이터가 힙구조 상태여야한다.

 

따라서 힙정렬 전에 데이터를 먼저 Heapify Algorithm으로 힙구조를 만든다.

(힙구조는 여러개 나올 수 있다.)

 

오름차순 정렬을 위해 Max Heap을 구성하여

Max Heap의 가장 끝에 해당하는 리프노드와

root를 Swap하면 가장 큰 값이 가장 끝에 위치하게 된다.

 

가장 끝에 가장 큰 값이 위치 했으므로

가장 끝의 위치를 N이라고 하면

N-1의 위치에 그 다음으로 가장 큰 값을 위치시키면 된다.

이후 부터 다시 Max Heap 만들고 리프와 루트의 Swap (N-1)번 작업하며 정렬하는 알고리즘이다.

 

참고 ↓
https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

 

1. 다음은 자료구조에서 많이 사용하고 있는 정렬 알고리즘이다. 다음 물음에 답하시오. (30점)

 

 

 

 

 

 

* 1차원 배열로 구성하는 완전이진트리의 중요한 특징

 

 

 

 

1차원 배열의 인덱스 값은 완전이진트리로 취급할 때 중요한 의미를 가진다.

위 예시 그림에서 root에 해당하는 인덱스 1의 값의 자식은 2와 3번 인덱스를 가진 노드가 된다.

 

1차원 배열로 표현한 완전이진트리에서는다음과 같이 일반화 할 수 있다.

 

1. 부모 노드의 인덱스 번호 P라고 할 때

 

A[P] 의 왼쪽 자식은 A[P*2]

오른쪽 자식은 A[P*2 +1]

 

2.자식 노드의 인덱스 번호를 C라고 할 때

 

부모는 A[C/2]

 

(1) 위의 알고리즘 AAASort와 BBB를 설명하시오. (12점)

 

 

답안 )

첫번째로,BBB는Heapify Algorithm에 해당한다. Heapify Algorithm은 최소힙, 또는 최대힙을 구성하는 알고리즘이다. 최대힙이라면 모든 부모-자식 관계에 대해서 자식의 값이 부모보다 큰 경우는 없는 것이다. 최소힙은 그 반대이며 자료구조의 형태는완전이진트리이다. 처음에 n/2부터 시작하는 이유는 처음 받은 데이터 Set에서 리프노드들은 볼 필요가 없이 부모부터 확인을 하겠다는 뜻이다. 이는 Heap을 만드는데 있어서 전혀 지장이 가지 않는다.

최초로 받은 데이터에 대해 최소, 또는 최대 힙을 구성한 후 힙정렬을 수행한다.

 

두번째로, AAASort는 Heap Sort에 해당한다. 데이터의 개수가 N개라면 다음과 같은 과정을 거친다. 여기서는 Max Heap을 쓴다.

 

Max Heap을 먼저 만든다.

 

 

Step 1. N번 째 자리와 root의 값을 Swap한다. root는 최대 값이고 N 번째는 가장 끝이므로 가장 큰 값이 가장 뒤로 가는 것이다. 즉, 가장 끝 N번째 자리의 값은 결정이 났다.

 

Step 2. 남은 N-1개의 데이터에 대해 Max Heap을 만든다. 다시 root는 최대 값이고 N-1 번째는 가장 끝의 직전 위치이므로 전체 데이터 중 두번째로 큰 값이 들어갈 위치이다. root와 N-1의 값을 Swap한다.

 

Step 3. 남은 N-2개의 데이터에 대해 Max Heap을 만든다. 다시 root는 최대 값이고 N-2 번째는 가장 끝의 직전의 직전 위치이므로 전체 데이터 중 세번째로 큰 값이 들어갈 위치이다. root와 N-2의 값을 Swap한다.

 

Step 4~ Final

위와 똑같은 작업을 반복하면 최종적으로 오름차순으로 정렬된 데이터를 구할 수 있게 된다.

 

 

(2) 위의 알고리즘에서 (가-1),(가-2),(나)에 들어갈 적합한 Pseudo Code를 표현하시오.(9점)

 

 

답안 )

 

다음은 Java로 표현한 Code이다.

 

    private static void AAASort(int[] a, int size){
        int n = size-1;
        int temp=0;
        for(int i = n/2; i>=2 ;i--) {//최초  Max heap
            BBB(a,i,n);
        }
        for(int i=n;i>=2;i--) {
            BBB(a,1,i);
            temp = a[1]; //1은 root고 힙구조를 만들었으므로 가장 꼭대기는 항상 최대값이 유지된다.
        
            /*
             * To write pseudo code
             */
            a[1] = a[i]; // (가-1)
            a[i] = temp; // (가-2)
        }
    }
 
    private static void BBB(int[] a, int h, int m) { 
        //Max Heap을 만든다. root부터 자식노드의 방향으로 하향식으로 Heap을 만든다.
        int imsi = a[h];//부모의 값
        int j = 0;
        for(j=2*h;j<=m;j=j*2){ //자식 확인 
            if(j<m) {
                if(a[j]<a[j+1]) {//왼쪽 자식과 오른쪽 자식 중 더 큰 자식을 포인팅 
                    j++;
                }
            }
            if(imsi>=a[j]) break;//부모보다 작거나 같으면 끝 
            else {//부모보다 크면 Swap
        
                /*
                 * To write pseudo code
                 */
                
                // (나) 
                a[h]=a[j];
                h=j;
            }
        }
        a[j/2]=imsi;
    }

 

 

(3) 위 알고리즘의 시간복잡도를 설명하시오 (9점)

 

답안 )

Heap 구조는 완전이진트리로써 N개의 데이터 중에서 가장 최소, 가장 최대 값을 Root로 올리는 과정

 

 

 

 

N개의 데이터를 하나씩 확인하면서Heap Sorting하는 과정

 

 

N개의 데이터 하나씩 root와 Swap하고 (N) 매번 다시 Heap을 형성 (logN)하기 때문에 최종적인 최악의 시간 복잡도는 결과적으로 다음과 같다.

 

 

 

Full Code (Java)

 

 

public class 변리사_3번 {
    public static void main(String[] args) {
        int[] data = new int[] {0,9,8,7,6,5,4,3,2,1};
        int[] data2 = new int[] {0,9,2,3,4,5,6,7,8,1};
        int[] data3 = new int[] {0,9,8,2,8,3,7,4,6,5};
        int[] data4 = new int[] {0,9,6,5,8,3,5,2,1,6};
        int[] data5 = new int[] {0,10,7,6,2,3,4,5,2,6};
        int size = data5.length;
        AAASort(data5,size);
        
    }
 
    private static void AAASort(int[] a, int size){
        int n = size-1;
        int temp=0;
        for(int i = n/2; i>=2 ;i--) {//최초  Max heap
            BBB(a,i,n);
        }
        for(int i=n;i>=2;i--) {
            BBB(a,1,i);
            temp = a[1]; //1은 root고 힙구조를 만들었으므로 가장 꼭대기는 항상 최대값이 유지된다.
        
            /*
             * To write pseudo code
             */
            a[1] = a[i]; // (가-1)
            a[i] = temp; // (가-2)
        }
    }
 
    private static void BBB(int[] a, int h, int m) { 
        //Max Heap을 만든다. root부터 자식노드의 방향으로 하향식으로 Heap을 만든다.
        int imsi = a[h];//부모의 값
        int j = 0;
        for(j=2*h;j<=m;j=j*2){ //자식 확인 
            if(j<m) {
                if(a[j]<a[j+1]) {//왼쪽 자식과 오른쪽 자식 중 더 큰 자식을 포인팅 
                    j++;
                }
            }
            if(imsi>=a[j]) break;//부모보다 작거나 같으면 끝 
            else {//부모보다 크면 Swap
        
                /*
                 * To write pseudo code
                 */
                
                // (나) 
                a[h]=a[j];
                h=j;
            }
        }
        a[j/2]=imsi;
    }
}

 

 

* 참고로 예시로 주어진 코드 중에 BBB(a,1,i-1)을 그대로 하는 경우 정렬이 제대로 안되는 결과가 나온다.

 

BBB(a,1,i)로 작성해야 실제로 정렬이 된다.

 

오리지널 코드를 고치지 않고 최대한 돌려보려고 많은 고생을 했으나 이에 대한 필자의 세 가지 궁금점을 남기고 해설을 마무리한다.

 

1. 가1,가2,나 칸에는 의사코드로만 넣어서 채점하기 때문에 예시 코드가 완벽한 코드가 아닐 수 있다.

 

2. 처음부터 예시 코드가 좀 잘못되었고, 오해의 여지가 있는 코드가 작성되어 있어서 이의제기가 가능하다?

 

3. 오리지널 코드가 돌도록 (나) 에서 요구되는 의사코드가 여러 라인이다?

 

 

github

 

https://github.com/Jangsukwoo/Algorithm/blob/master/Algo/src/CodingAcademy/%EB%B3%80%EB%A6%AC%EC%82%AC_3%EB%B2%88.java

Jangsukwoo/Algorithm

 

참고

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙 정렬 - 위키백과, 우리 모두의 백과사전