병합정렬, 힙정렬(Merge sorte, Heap sort)

병합정렬

‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법으로일반적으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.

분할 정복(divide and conquer) 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

병합 정렬(merge sort) 알고리즘의 구체적인 개념

 

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
병합 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
병합 정렬은 과정에서 추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합(merge)하는 단계 이다.

 

---

힙정렬(Heapsort)

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

힙

힙은 트리의 일종이지만 조금 특이한 성질을 가지고 있다. 힙에는 최대힙과 최소힙이 있는데, 일단 최대힙의 정의는 다음과 같다. 

완전 트리이면서 Root가 모든 경우에 자식들보다 커야한다.

최소힙은 Root가 자식보다 작으면 된다. 그리고 완전 트리란 바로 노드가 순서대로 들어있는 트리가 완전 트리로, 왼쪽에서부터 차곡차곡 들어가는 트리다. 한 줄이 다 찼으면 다음 줄 왼쪽에 노드가 들어간다. 

Root가 자식보다 커야한다는 뜻은 다음과 같은 트리를 의미한다. 트리 안의 서브트리에도 이 규칙이 적용된다. 또한 완전 트리이기 때문에 지난 시간처럼 트리로 만들지 않고 배열로 만들어도 된다. 다음 트리와 다음 배열은 같은 것이다다.

힙은 제거할 때 가장 위의 루트값이 빠진다. 루트 값은 최대힙이면 숫자 중에 가장 큰 값, 최소힙이면 가장 작은 값이 루트가 된다.

 

알고리즘

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

시간복잡도

이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 {\displaystyle O(\log n)}

의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 {\displaystyle n}

개의 데이터 삭제 및 재구성 시간을 포함한다.

시간 복잡도는

=(\log n+\log(n-1)+...+log2)

=(\log n+\log(n-1)+...+\log 2)+(\log n+\log(n-1)+...+\log 2)

=(n\log n)}

따라서 힙 정렬은 일반적인 경우 O(n\log n)

의 시간복잡도를 가진다.