이전 게시글에 이어 이번에는 Quick Sort, Merge Sort, Heap Sort를 설명해보려 한다.
Quick Sort
Quick Sort의 개념
Quick Sort는 분할 정복(Divide and Conquer) 전략으로 정렬을 한다. 분할 정복이란 문제를 2개의 작은 부분 문제로 분리하고 각각을 해결한 뒤, 그 결과를 모아 원래의 큰 문제를 해결하는 전략이다. Quick Sort가 분할 정복 전략을 이용하는 것은 Quick Sort가 진행되는 과정을 보면 이해가 가능하다.
오름차순 정렬을 Quick Sort로 수행하는 과정은 다음과 같다.
- 리스트 안에 있는 임의의 한 요소를 선택하는데, 이를 pivot이라고 한다.
- pivot을 기준으로 pivot보다 작은 요소들은 pivot의 왼쪽으로 옮기고, pivot보다 큰 요소들은 pivot의 오른쪽으로 옮긴다.
- pivot을 제외한 왼쪽 부분 리스트와 오른쪽 부분 리스트에도 위의 과정을 반복한다.
- 부분 리스트의 크기가 0이나 1이 될 경우 종료한다.
위 과정을 보면 pivot을 기준으로 리스트를 2개의 작은 부분 리스트로 나누고, 나뉘어진 부분 리스트에서 대해 같은 과정을 반복한다. 만약 부분 리스트의 크기가 0이나 1이라면, 해당 부분은 이미 정렬이 되어있는 것이므로 반복을 종료한다. 이 과정을 분할 정복의 관점에서 보자면 다음과 같다.
- 분할(Devide): pivot을 기준으로 리스트를 2개의 부분 리스트로 분할한다.
- 정복(Conquer): 부분 리스트를 정렬하며, 해당 부분 리스트의 크기가 1보다 크다면 다시 분할한다.
- 결합(Combine): 정렬이 된 부분 리스트를 하나의 배열로 결합한다.
다만 Quick Sort의 경우 추가적인 메모리를 사용하지 않고 같은 리스트 내에서 정렬을 수행하기 때문에 따로 결합 과정을 구현할 필요는 없다.
Quick의 구현 코드
low와 high 변수를 통해 리스트를 순회하며 pivot보다 작은 값은 왼쪽, pivot보다 큰 값은 오른쪽 부분 리스트에 위치시킨다. 이후, quickSort(arr, left, high - 1)과 quickSort(arr, high + 1, right)를 호출해 두 부분 리스트에 대해 다시 정렬을 실시한다.
#define SWAP(x, y, tmp) ( (tmp) = (x), (x)=(y), (y)=(tmp) )
// Quick Sort의 구현
// 오름차순 정렬을 기준으로 설명
// 1. pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽으로 옮긴다.
// 2. pivot을 제외한 왼쪽 부분 리스트와 오른쪽 부분 리스트에도 위 과정을 반복한다.
// 3. 부분 리스트의 크기가 0 또는 1이 될 경우 종료한다.
// int arr[] : 정렬할 1차원 배열
// int left : 정렬할 배열의 첫번째 인덱스
// int right : 정렬할 배열의 마지막 인덱스
void quickSort(int arr[], int left, int right){
// 정렬할 배열의 크기가 2이상일 경우 수행.
// left == right 일 경우, 원소가 하나이므로 항상 정렬된 상태
if (left < right){
int tmp; // SWAP을 위한 임시 변수
int pivot = left; // pivot은 가장 왼쪽 값으로 결정.
int low = left;
int high = right + 1;
do{
// low가 배열의 범위를 벗어나거나, arr[low]가 arr[pivot]보다 크거나 같은 경우 탈출.
do {
low++;
} while(low <= right && arr[low] < arr[pivot]);
// high가 배열의 범위를 벗어나거나, arr[high]가 arr[pivot]보다 작거나 같은 경우 탈출.
do {
high--;
} while(high >= left && arr[high] > arr[pivot]);
// 위의 두개의 반복문을 통해
// arr[low]에는 pivot보다 큰 값이 arr[high]에는 pivot보다 작은 값이 들어있다.
// 만약 low < high인 경우 정렬이 되어있지 않다는 것이므로 서로 바꿔줌.
if (low < high){
SWAP(arr[low], arr[high], tmp);
}
} while(low < high);
// pivot 값을 기준으로 왼쪽에 작은 값들을 오른쪽에 큰값들을 몰기위한 SWAP
SWAP(arr[pivot], arr[high], tmp);
// pivot을 기준으로 왼쪽에는 작은 값들, 오른쪽에는 큰 값들이 위치함.
// 이 두 배열에 대해서도 정렬을 시작함.
quickSort(arr, left, high - 1);
quickSort(arr, high + 1, right);
}
}아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
#define SWAP(x, y, tmp) ( (tmp) = (x), (x)=(y), (y)=(tmp) )
template <typename T>
bool defaultCompare(T a, T b){
return a <= b;
}
// Quick Sort의 구현
// 오름차순 정렬을 기준으로 설명
// 1. pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽으로 옮긴다.
// 2. pivot을 제외한 왼쪽 부분 리스트와 오른쪽 부분 리스트에도 위 과정을 반복한다.
// 3. 부분 리스트의 크기가 0 또는 1이 될 경우 종료한다.
// T arr[] : 정렬할 1차원 배열
// int left : 정렬할 배열의 첫번째 인덱스
// int right : 정렬할 배열의 마지막 인덱스
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
void quickSort(T arr[], int left, int right, bool (*compare)(T, T) = defaultCompare){
// 정렬할 배열의 크기가 2이상일 경우 수행.
// left == right 일 경우, 원소가 하나이므로 항상 정렬된 상태
if (left < right){
T tmp; // SWAP을 위한 임시 변수
int pivot = left; // pivot은 가장 왼쪽 값으로 결정.
int low = left;
int high = right + 1;
do{
// low가 배열의 범위를 벗어나거나, arr[low]가 arr[pivot]보다 크거나 같은 경우 탈출.
do {
low++;
} while(low <= right && arr[low] < arr[pivot]);
// high가 배열의 범위를 벗어나거나, arr[high]가 arr[pivot]보다 작거나 같은 경우 탈출.
do {
high--;
} while(high >= left && arr[high] > arr[pivot]);
// 위의 두개의 반복문을 통해
// arr[low]에는 pivot보다 큰 값이 arr[high]에는 pivot보다 작은 값이 들어있다.
// 만약 low < high인 경우 정렬이 되어있지 않다는 것이므로 서로 바꿔줌.
if (low < high){
SWAP(arr[low], arr[high], tmp);
}
} while(low < high);
// pivot 값을 기준으로 왼쪽에 작은 값들을 오른쪽에 큰값들을 몰기위한 SWAP
SWAP(arr[pivot], arr[high], tmp);
// pivot을 기준으로 왼쪽에는 작은 값들, 오른쪽에는 큰 값들이 위치함.
// 이 두 배열에 대해서도 정렬을 시작함.
quickSort(arr, left, high - 1);
quickSort(arr, high + 1, right);
}
}Quick Sort의 시간복잡도
Quick Sort는 기존의 리스트의 크기가 n이라고 할 때 나뉘어지는 두 부분 리스트의 크기가 n/2인 경우 최선의 경우가 된다. 이 때의 시간복잡도는 O(재귀 호출의 깊이 * 각 호출마다 비교 횟수가 된다.
Quick Sort에서 분할이 종료되는 시점, 다시 말해 재귀 호출이 종료되는 시점은 리스트의 크기가 1이하가 되는 경우이다. 리스트의 크기 n이 2의 거듭제곱(n=2^k)이라 가정하였을 때, 재귀 함수가 호출될 때마다 n의 크기는 절반씩 줄어들어 k번의 호출에서 재귀 호출이 종료된다. 즉 재귀 호출의 깊이는 k가 되며, k는 log2n이 된다.
각 호출마다 비교 횟수는 전체 리스트의 대부분을 비교해야 하므로 평균적으로 n이 된다.
즉, 시간복잡도가 O(nlog2n)이 된다.
Quick Sort의 최악의 경우는 리스트가 이미 정렬이 되어 있는 경우이다. 이 경우 리스트가 매우 불균형하게 나뉘어 지는데, 리스트의 가장 왼쪽 원소를 pivot으로 정할 경우 왼쪽 부분 리스트의 크기는 0, 오른쪽 부분 리스트의 크기는 n-1이 된다.
한번의 재귀 호출당 n이 1씩만 줄어들기 때문에 재귀 호출의 깊이는 n이 된다. 각 호출마다 비교 횟수는 여전히 n이기에, 시간복잡도가 O(n2)이 된다.
평균적으로는 O(nlog2n)이 된다.
Quick Sort의 특징
Quick Sort의 가장 큰 특징은 이름에서 유추가 가능하듯이 빠르다는 것이다. 물론 모든 경우에 대해 빠른 것은 아니지만, 시간 복잡도가 O(nlog2n)을 가지는 정렬 알고리즘들 중에서 대부분의 경우 가장 빠르다. 그러나 시간복잡도 파트에서 설명하였듯이, 경우에 따라 부분 리스트의 분할이 매우 불균등하게 이루어 질 수 있으며, 이 때문에 매우 느려질 수 있다.
또한, Quick Sort의 경우 아래에서 설명할 Merge Sort와 다르게 추가적인 배열을 필요로 하지 않는다.
마지막으로 Quick Sort는 Unstable Sort에 속한다.
Merge Sort
Merge Sort의 개념
1개의 리스트를 2개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 뒤, 2개의 부분 리스트를 다시 결합하여 정렬하는 방식이다. 분할하고, 정렬하고, 결합한다라는 말에서 알 수 있듯이 Merge Sort는 분할 정복(Divide and Conquer) 전략을 사용한다.
오름차순 정렬을 Merge Sort로 진행하는 과정은 다음과 같다.
- 정렬되지 않은 리스트를 절반으로 잘라 2개의 부분 리스트로 나눈다.
1-1. 만약 부분 리스트의 크기가 2 이상이라면 1의 과정을 반복한다.
1-2. 만약 부분 리스트의 크기가 0 또는 1이라면, 정렬된 것으로 본다. - 정렬이 된 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
위 과정에서 볼 수 있듯, 분할하고 정렬한 뒤 결합하는 과정을 통해 분할 정복 전략을 사용했음을 알 수 있다.
Merge Sort의 구현 코드
mergeSort() 에서는 리스트를 절반으로 쪼개는 분할 과정을 수행하며, 부분 리스트의 크기가 1 이하로 쪼개진 경우에는 merge()를 호출하여 재귀적으로 합병해나간다.
merge()에서는 정렬 및 합병 과정이 이루어지며, Merge Sort의 경우 합병하는 과정에서 추가 메모리가 필요하기에 tmp[] 배열을 할당했다.
// Merge Sort에서 분할된 부분 배열을 합병하는 과정
// Merge Sort에서 첫번째 인덱스가 left, 마지막 인덱스가 right인 한 배열을 mid를 기준으로 두 개로 쪼개었다.
// 이 쪼개진 두 배열을 합병하는 것이며, 합병 과정에서 정렬이 이루어진다.
// int arr[] : 정렬할 1차원 배열
// int left : 합병할 두 배열 중 왼쪽 배열의 첫번째 인덱스
// int mid : 합병할 두 배열의 중간 인덱스 -> 왼쪽 배열의 마지막 인덱스 + 1이면서 오른쪽 배열의 첫번째 인덱스이다.
// int right : 합병할 두 배열 중 오른쪽 배열의 마지막 인덱스
void merge(int arr[], int left, int mid, int right){
int i = left;
int j = mid + 1;
int cur = 0;
int *tmp = new int[right - left + 1]; // merge sort는 추가 메모리가 필요함.
// 분할된 부분 배열을 각각 탐색하면서 더 작은 값을 먼저 임시 배열에 넣어준다.
while(i <= mid && j <= right){
if (arr[i] <= arr[j])
tmp[cur++] = arr[i++];
else
tmp[cur++] = arr[j++];
}
// 만약 왼쪽 부분이 남아있다면, 그 값들을 임시 배열에 넣어줌
while(i <= mid){
tmp[cur++] = arr[i++];
}
// 만약 오른쪽 부분이 남아있는 경우는 원래 배열(arr)에 정렬된 상태로 저장되어있기 때문에 옮길 필요가 없다.
// 임시 배열에 있는 정렬된 값을 원래 배열에 넣어준다.
for(int idx = 0; idx < cur; idx++){
arr[left + idx] = tmp[idx];
}
delete[] tmp;
}
// Merge Sort의 구현
// 분할 정복(Divide and Conquer) 방법으로 정렬을 수행한다.
// 문제를 2개 이상의 부분 문제로 분할하고, 각각을 해결한 뒤 결과를 모아 합병하는 방식이다.
// int arr[] : 정렬할 1차원 배열
// int left : 정렬할 배열의 첫번째 인덱스
// int right : 정렬할 배열의 마지막 인덱스
void mergeSort(int arr[], int left, int right){
if (left < right){
int mid = (left + right) / 2;
// 리스트를 중간을 기준으로 두개로 분할함
mergeSort(arr, left, mid, compare);
mergeSort(arr, mid + 1, right, compare);
// 분할한 리스트를 합병하며 정렬함.
merge(arr, left, mid, right, compare);
}
}아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
// Merge Sort에서 분할된 부분 배열을 합병하는 과정
// Merge Sort에서 첫번째 인덱스가 left, 마지막 인덱스가 right인 한 배열을 mid를 기준으로 두 개로 쪼개었다.
// 이 쪼개진 두 배열을 합병하는 것이며, 합병 과정에서 정렬이 이루어진다.
// T arr[] : 정렬할 1차원 배열
// int left : 합병할 두 배열 중 왼쪽 배열의 첫번째 인덱스
// int mid : 합병할 두 배열의 중간 인덱스 -> 왼쪽 배열의 마지막 인덱스 + 1이면서 오른쪽 배열의 첫번째 인덱스이다.
// int right : 합병할 두 배열 중 오른쪽 배열의 마지막 인덱스
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
void merge(T arr[], int left, int mid, int right, bool (*compare)(T, T)){
int i = left;
int j = mid + 1;
int cur = 0;
T *tmp = new T[right - left + 1]; // merge sort는 추가 메모리가 필요함.
// 분할된 부분 배열을 각각 탐색하면서 더 작은 값을 먼저 임시 배열에 넣어준다.
while(i <= mid && j <= right){
if (arr[i] <= arr[j])
tmp[cur++] = arr[i++];
else
tmp[cur++] = arr[j++];
}
// 만약 왼쪽 부분이 남아있다면, 그 값들을 임시 배열에 넣어줌
while(i <= mid){
tmp[cur++] = arr[i++];
}
// 만약 오른쪽 부분이 남아있는 경우는 원래 배열(arr)에 정렬된 상태로 저장되어있기 때문에 옮길 필요가 없다.
// 임시 배열에 있는 정렬된 값을 원래 배열에 넣어준다.
for(int idx = 0; idx < cur; idx++){
arr[left + idx] = tmp[idx];
}
delete[] tmp;
}
// Merge Sort의 구현
// 분할 정복(Divide and Conquer) 방법으로 정렬을 수행한다.
// 문제를 2개 이상의 부분 문제로 분할하고, 각각을 해결한 뒤 결과를 모아 합병하는 방식이다.
// T arr[] : 정렬할 1차원 배열
// int left : 정렬할 배열의 첫번째 인덱스
// int right : 정렬할 배열의 마지막 인덱스
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
void mergeSort(T arr[], int left, int right, bool (*compare)(T, T) = defaultCompare){
if (left < right){
int mid = (left + right) / 2;
// 리스트를 중간을 기준으로 두개로 분할함
mergeSort(arr, left, mid, compare);
mergeSort(arr, mid + 1, right, compare);
// 분할한 리스트를 합병하며 정렬함.
merge(arr, left, mid, right, compare);
}
}Merge Sort의 시간복잡도
Merge Sort의 시간복잡도는 O(재귀 호출의 깊이 * 각 호출마다 비교 횟수와 이동 횟수)로 볼 수 있다.
Merge Sort는 리스트를 절반으로 자르기 때문에, 리스트의 원소의 개수로 재귀 호출의 깊이를 알 수 있다. 원소의 개수가 n = 2^k일 때, 절반으로 자를 때마다 2^(k-1), 2^(k-2), ..., 2^1, 2^0으로 줄어든다. 1또는 0까지 줄어드는데 걸리는 횟수는 k번이고 k = log2n이므로 재귀 호출의 깊이는 log2n이 된다.
각 호출마다 비교 횟수는 크기가 n/2인 두 부분 리스트를 비교한다면 최대 n번이 된다. 이동 횟수의 경우, Merge Sort는 임시 배열을 통해 원소를 이동하므로 한 원소에 대해 이동이 두번 이루어진다. 즉 n개의 원소를 옮기는데 2n번의 이동이 이루어진다.
비교 횟수와 이동 횟수를 합하면 3n이 된다.
즉, Merge Sort의 시간복잡도는 O(3n * log2n) = O(nlog2n)이 된다.
Merge Sort의 특징
Merge Sort는 Quick Sort와 유사하지만 차이점이 몇가지 있다. 차이점은 우선 Quick Sort는 pivot을 기준으로 리스트를 나누기 때문에 두 부분 리스트가 불균등하게 나뉠 수 있지만, Merge Sort는 두 부분 리스트를 균등한 크기로 나눈다는 것이다.
또 하나의 차이점은, Merge Sort는 정렬을 할 때 추가적인 메모리 공간을 필요로 한다는 것이다. Merge Sort는 정렬된 두 부분 리스트를 결합할 때 추가적인 리스트를 사용하여 결합을 진행한다.
Heap Sort
Heap Sort의 개념
Heap Sort를 설명하려면 Heap에 대해 먼저 알아야 한다.
Heap이란 Complete Binary Tree의 일종으로 최대값 및 최소값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조이다. Heap에는 두가지 종류가 있으며, 최대 값이 먼저 나오는 경우 최대 힙(Max Heap), 최소 값이 먼저 나오는 경우 최소 힙(Min Heap)이라 부른다. Heap이라는 것이 최대값과 최소값을 찾아내는 연산을 위해 고안된 자료구조이기 때문에, 이를 이용한다면 원소들을 정렬하는 것 역시 빠르게 수행할 수 있다.
Heap Sort에서 오름차순 정렬을 할 때는 최소 힙을 사용하고, 내림차순 정렬을 할 때는 최대 힙을 사용하면 된다. Heap Sort의 정렬과정은 다음과 같다.
- 정렬해야할 리스트의 요소들로 힙을 만든다.
- 힙에서 원소를 하나씩 꺼내어 배열에 차례차례 저장한다.
Heap Sort의 구현 코드
Min Heap을 이용하여 오름차순 Heap Sort를 구현하였다. 리스트 안 n개의 원소를 Min Heap에 넣어준 후, n개의 원소를 차례차례 빼가며 리스트에 넣어줌으로써 정렬을 수행한다.
// Heap Sort의 구현
// Heap을 이용한 정렬이며 오름차순 정렬을 구현함.
// 배열의 원소 n개를 heap에 넣은 뒤, 하나씩 빼면서 정렬함
// int arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
void heapSort(int arr[], int n){
// 배열로 만든 heap은 인덱스 1부터 값이 들어감. 그렇기 때문에, 크기를 n + 1로 해줌.
int *heap = new int[n + 1];
// heap 초기화. 원소의 개수를 0으로 설정
heap[0] = 0;
// n개의 원소를 heap에 넣어줌.
for(int i = 0; i < n; i++){
insert_min_heap(heap, arr[i]);
}
// n개의 원소를 차례차례 빼주면서 배열에 넣어줌.
for(int i = 0; i < n; i++){
arr[i] = delete_min_heap(heap);
}
// heap에 할당된 메모리 해제.
delete[] heap;
}
// Insertion in Min Heap
// min heap에 value를 넣어줌.
// int heap[] : heap
// int value : heap에 넣을 값
void insert_min_heap(T heap[], T value){
// heap의 가장 마지막에 원소를 넣음.
int cur = ++(heap[0]);
// 삽입할 원소와 부모 노드를 비교하면서 삽입할 원소의 값이 더 작다면 위치를 바꿔줌.
while(cur != 1 && value < heap[cur / 2]){
heap[cur] = heap[cur / 2];
cur /= 2;
}
// 새로운 노드를 올바른 위치에 삽입함.
heap[cur] = value;
}
// Deletion in Min Heap
// min heap에서 최소 값을 삭제 및 반환해줌.
// int heap[] : heap
int delete_min_heap(int heap[]){
int parent, child;
int item, last;
item = heap[1]; // 루트 노드 값을 반환.
// heap의 마지막 값을 루트 노드 위치부터 비교해가며 삽입하기 적절한 위치를 찾을 것임.
last = heap[(heap[0])--];
parent = 1;
child = 2;
// child가 heap의 크기를 초과하면 탈출
while(child <= heap[0]){
// 오른쪽 자식이 왼쪽 자식보다 작다면, 오른쪽 자식을 대상으로 진행
if (child < heap[0] && heap[child + 1] < heap[child]){
child++;
}
// 만약 마지막 노드가 자식 노드보다 작다면, break
if (last < heap[child]){
break;
}
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = last;
return item;
}
아래 코드는 template과 compare파라미터를 이용하여 함수를 좀더 범용적으로 만든 코드이다. compare 파라미터에 넣은 비교함수에 따라 정렬되는 방식이 바뀐다.
// Heap Sort의 구현
// Heap을 이용한 정렬
// 배열의 원소 n개를 heap에 넣은 뒤, 하나씩 빼면서 정렬함
// T arr[] : 정렬할 1차원 배열
// int n : 배열 안 원소의 개수
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
void heapSort(T arr[], int n, bool (*compare)(T, T) = defaultCompare){
// 배열로 만든 heap은 인덱스 1부터 값이 들어감. 그렇기 때문에, 크기를 n + 1로 해줌.
T *heap = new T[n + 1];
// heap 초기화. 원소의 개수를 0으로 설정
heap[0] = 0;
// n개의 원소를 heap에 넣어줌.
for(int i = 0; i < n; i++){
insert_heap(heap, arr[i], compare);
}
// n개의 원소를 차례차례 빼주면서 배열에 넣어줌.
for(int i = 0; i < n; i++){
arr[i] = delete_heap(heap, compare);
}
// heap에 할당된 메모리 해제.
delete[] heap;
}
// Insertion in Heap
// heap에 value를 넣어줌.
// T heap[] : heap
// T value : heap에 넣을 값
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
void insert_heap(T heap[], T value, bool (*compare)(T, T)){
// heap의 가장 마지막에 원소를 넣음.
int cur = ++(heap[0]);
// 삽입할 원소와 부모 노드를 비교하면서 삽입할 원소의 우선순위가 높다면 위치를 바꿔줌.
while(cur != 1 && compare(value, heap[cur / 2])){
heap[cur] = heap[cur / 2];
cur /= 2;
}
// 새로운 노드를 올바른 위치에 삽입함.
heap[cur] = value;
}
// Deletion in Heap
// heap에서 우선순위가 큰 값을 삭제 및 반환해줌.
// T heap[] : heap
// bool (*compare)(T, T) : 원소를 비교해주는 비교 함수
template<typename T>
T delete_heap(T heap[], bool (*compare)(T, T)){
int parent, child;
T item, last;
item = heap[1]; // 루트 노드 값을 반환.
// heap의 마지막 값을 루트 노드 위치부터 비교해가며 삽입하기 적절한 위치를 찾을 것임.
last = heap[(heap[0])--];
parent = 1;
child = 2;
// child가 heap의 크기를 초과하면 탈출
while(child <= heap[0]){
// 오른쪽 자식이 왼쪽 자식보다 우선순위가 크면, 오른쪽 자식을 대상으로 진행
if (child < heap[0] && compare(heap[child + 1], heap[child])){
child++;
}
// 만약 마지막 노드가 자식 노드보다 우선순위가 크거나 같다면, break
if (!compare(heap[child], last)){
break;
}
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = last;
return item;
}
Heap Sort의 시간복잡도
Heap Sort는 Heap을 이용한 정렬이기 때문에, Heap의 시간복잡도와 큰 연관이 있다.
하나의 요소를 Heap에 삽입하거나 삭제하는데 걸리는 시간복잡도는 O(log2n)이다. 그리고 삽입 및 삭제해야할 요소의 개수가 n개이기 때문에 최종적인 시간복잡도는 O(nlog2n)이다.
heap Sort의 특징
Heap은 최대 값 혹은 최소 값을 쉽게 찾을 수 있기 때문에, 자료들 중 가장 큰 값 몇개 혹은 가장 작은 값 몇개를 찾을 때 매우 유용하다.
