알고리즘 분석 | 힙 정렬 | 분할 정복 Divide & Conquer | 병합 정렬 Merge sort

이전 포스팅

알고리즘 분석 | Heap 힙 데이터 구조 | Heap 삽입과 삭제

---

 

힙 정렬이란

Heap 정렬은 이진 트리(binary tree) 기반의 정렬 알고리즘으로, 최소 힙(min heap) 또는 최대 힙(max heap)을 이용하여 정렬을 수행하는 알고리즘입니다. 정렬되지 않은 원소들을 힙에 넣는 과정과 원소들을 정렬된 배열에 저장하는 과정을 번갈아 가며 수행합니다. 이렇게 하면, 가장 작은 값부터 차례대로 정렬된 배열에 저장됩니다.

Heap 정렬의 시간 복잡도는\( O(nlogn)\)으로, 대부분의 경우에 빠르고 효율적인 정렬 알고리즘 중 하나입니다.

 

정렬 과정

정렬 과정은 다음과 같습니다:

정렬되지 않은 원소들을 최대 힙(max heap)이나 최소 힙(min heap)으로 구성합니다.

• 최대 힙(max heap)은 부모 노드가 자식 노드보다 큰 값을 가지는 이진 트리입니다.
• 최소 힙(min heap)은 부모 노드가 자식 노드보다 작은 값을 가지는 이진 트리입니다.

1. 최대 힙(max heap)이나 최소 힙(min heap)에서 루트 노드(최대 값이나 최소 값)를 제거합니다.
2. 제거된 노드를 정렬된 원소들의 리스트에 추가합니다.
3. 1~3 단계를 반복하여, 모든 원소들을 정렬된 리스트에 추가합니다.

이 과정을 간략하게 설명하면, 이전 포스팅에서 배운 힙 자료 구조의 성질을 이용하는 것 입니다.

 

힙 자료구조의 성질로 인해 가장 작은 값이 맨 위로 올라오게 되는데,

그 값을 제거하고 배열에 넣고, 다시 작은 값이 맨위로 올라오게 정렬되면 제거하고 배열에 넣는 이 과정을 계속 반복하면

결국 배열에는 가장 작은 값부터 차례대로 정렬되게 됩니다

---

 

분할 정복(Divide & Conquer)

Merge 정렬을 이해하기 전에 분할정복이라는 것을 공부해볼 수 있는데,

분할정복(Divide-and-Conquer) 방법은 일부 알고리즘 문제를 해결하는 데 사용할 수 있는 방법 중 하나입니다. 이 방법은 큰 문제를 작은 문제로 나누어 해결하고, 이들을 결합하여 원래 문제를 해결하는 전략입니다.

분할정복 방법은 일반적으로 다음과 같은 세 가지 단계로 구성됩니다:

 

1. 분할(Divide)

• 입력 데이터를 더 이상 분할할 수 없을 정도로 작아질 때까지, 두 개 이상의 부분 문제로 분할합니다.
• 이 때, 분할된 부분 문제들은 원래 문제와 독립적이며, 서로 중복되지 않는 데이터를 가집니다.

2. 정복(Conquer)

• 분할된 부분 문제들을 재귀적으로 해결합니다.
• 부분 문제들이 충분히 작아지면, 더 이상 분할할 수 없을 정도로 작아졌으므로, 
• 각각의 부분 문제들을 직접 해결합니다.

3. 결합(Combine)

• 부분 문제들의 해답을 결합하여 전체 문제의 해답을 구합니다.
• 이 때, 각 부분 문제들의 해답이 서로 올바르게 결합되어야 전체 문제의 해답이 올바르게 구해집니다.
• 즉, 분할정복 방법은 큰 문제를 작은 문제들로 분할하고, 작은 문제들을 해결하며, 이를 결합하여 전체 문제를 해결하는 방법입니다. 

이 방법을 이용하면 대부분의 문제를 더 효율적으로 해결할 수 있습니다. 예를 들어, 정렬, 검색, 그래프 탐색 등의 알고리즘 문제들은 분할정복 방법을 이용하여 해결할 수 있습니다.

---

 

병합 정렬(Merge sort)

병합 정렬(mergesort)은 분할정복(divide-and-conquer) 방법을 이용한 정렬 알고리즘 중 하나입니다. 다음과 같은 단계로 이루어집니다:

• 분할(Divide): 정렬되지 않은 배열을 반으로 분할합니다.
• 정복(Conquer): 각각의 부분 배열을 재귀적으로 병합 정렬합니다.
• 결합(Combine): 정렬된 두 개의 부분 배열을 하나의 정렬된 배열로 병합합니다.

Fig. 1. 병합 정렬

 

1. 병합 정렬은 정렬되지 않은 배열을 분할하고, 
2. 각각의 부분 배열을 재귀적으로 정렬합니다. 
3. 그리고, 정렬된 두 개의 부분 배열을 병합하여 하나의 정렬된 배열을 생성합니다. 

 

이 과정은 각각의 부분 배열이 하나의 원소만 남을 때까지 반복되며, 결국에는 전체 배열이 정렬됩니다.

병합 정렬의 시간 복잡도는 항상 \(O(nlogn)\)으로 일정하며, 최선, 평균, 최악 모든 경우에 대해 동일합니다. 따라서, 병합 정렬은 대부분의 경우에 빠르고 효율적인 정렬 알고리즘 중 하나입니다.

---