ing Algorithm - Quick Sort, Merge Sort, Heap Sort

これまでの投稿に続いて、今回はクイックSort、Merge Sort、HeapSortをご紹介します.
Quick Sort
クイックソフトウェアの概念
Quick Sortは、パーティションとクエリーポリシーを使用してソートされます.分割征服とは,問題を二つの小さな部分に分け,それぞれ解決した後,結果を集中して元の大きな問題を解決する戦略である.高速ソフトウェアは分割征服戦略を採用し,高速ソフトウェアのプロセスから理解できる.
高速Sortを使用して昇順ソートを実行する手順は、次のとおりです.

リストの任意の要素をpivotと呼びます.

支点を基準として、支点より小さい要素は支点の左側に移動し、支点より大きい要素は支点の右側に移動する.

pivotのほか、左側リストと右側リストも上記の手順を繰り返します.

部分リストのサイズが0または1の場合に終了します.

上記の手順に従ってpivotを基準にリストを2つの小さな部分リストに分け,各部分リストで同じ手順を繰り返す.部分リストのサイズが0または1の場合、部分はソートされ、重複が終了します.分割征服の観点から見ると、この過程は以下の通りである.

分割:pivotを基準にリストを2つの部分リストに分割します.

征服(Conquer):部分リストをソートし、その部分リストのサイズが1より大きい場合、再分割します.

マージ(Combine):ソートされたリストの一部を配列にマージします.

ただし、高速Sortでは、追加のメモリを使用する必要はなく、同じリストでソートするため、マージプロセスを実装する必要はありません.
迅速な実装コードlowおよびhigh変数によってリストを巡回し、pivot未満の値は左側にあり、pivotより大きい値は右側にある.その後、quickSort(arr, left, high - 1)およびquickSort(arr, high + 1, right)を呼び出して、2つの部分リストを再ソートする.

#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);
    }
}

高速起動の時間的複雑さ
既存のリストのサイズがnの場合、2つの部分リストのサイズがn/2の場合、高速起動が最適になります.このときの時間的複雑度はO(재귀 호출의 깊이 * 각 호출마다 비교 횟수であった.
高速Sortでは,分割終了時,すなわち再帰呼び出し終了時にリストのサイズが1より小さい.リストのサイズnが2の複数回の二乗(n=2^k)であると仮定し、再帰関数を呼び出すたびにnのサイズが半分に減少し、k回の呼び出しで再帰呼び出しが終了する.すなわち,再帰呼び出しの深さはk,kはlog 2 nである.
各呼び出しの比較回数は、リスト全体の大部分を比較する必要があるため、平均はnである.
すなわち,時間的複雑度はO(nlog 2 n)である.
ファストSortの最悪のケースはリストがソートされていることです.この場合、リストは非常に不均衡であり、リストの最も左側の要素をpivotとして指定すると、左側のリストのサイズは0、右側のリストのサイズはn-1となる.
再帰呼び出しnは、毎回1だけ減少するので、再帰呼び出しの深さはnである.各呼び出しの比較回数は依然としてnであり,時間複雑度はO(n 2)である.
平均はO(nlog 2 n)であった.
クイックソフトウェア機能
ファストソフトの最大の特徴は、名前から推測できるほど速いことです.もちろんすべての場合が速いわけではないが,時間的複雑度がO(nlog 2 n)のソートアルゴリズムでは,ほとんどの場合が最も速い.しかし、時間的複雑さの部分で説明したように、場合によっては、部分リストの分割が非常に不均一になり、非常に遅くなる可能性があります.
また、高速Sortについては、後述するMerge Sortに示すように、追加の配列は不要である.
最後に、Quick SortはUnstable Sortに属する.
Merge Sort
Merge Sortの概念
1つのリストを2つのサイズの等しいリストに分割し、分割された部分リストをソートし、2つの部分リストと組み合わせてソートします.분할하고, 정렬하고, 결합한다という言葉から分かるように、Merge SortはパーティションとConquerポリシーを使用しています.
Merge Sortで昇順ソートする手順は、次のとおりです.

の並べ替えられていないリストを半分に切り、2つの部分リストに分けます.
1-1. 部分リストのサイズが2より大きい場合は、1のプロセスを繰り返します.
1-2. 一部のリストのサイズが0または1の場合は、ソート済みとみなされます.

ソート後の2つの部分リストを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=log 2 nであるため、再帰呼び出しの深さはlog 2 nである.
各呼び出しの比較回数は最大n回であり、比較サイズがn/2の2つの部分リストである場合.移動回数の場合、Merge Sortは一時配列で要素を移動するので、1つの要素を2回移動します.すなわち,n個の要素を移動し,2 n回の移動を行う.
比較回数と移動回数を合わせて3 nです.
すなわち,Merge Sortの時間的複雑度はO(3 n*log 2 n)=O(nlog 2 n)である.
Merge Sortの特徴
Merge SortはQuick Sortと似ていますが、いくつかの違いがあります.違いは、高速Sortはまずpivotを基準としてリストを分割するため、2つの部分リストが不均一である可能性があり、Merge Sortは2つの部分リストを等しいサイズに分割することである.
もう1つの違いは、MergeSortがソート時に追加のメモリ領域を必要とすることです.Merge Sortは、2つのソートされた部分リストをマージするときに、追加のリストを使用してマージします.
Heap Sort
Heap Sortのコンセプト
HeapSortについて説明するには、まずHeapについて知ります.
Heapは完全な二叉木で、最大値と最小値を迅速に検索するために設計されたデータ構造です.heapには2つのタイプがあり、最大値が先に現れた場合を最大heap、最小値が先に現れた場合を最小heapと呼ぶ.Heapは最大値と最小値を探すために設計されたデータ構造であり、それを利用すれば要素のソートも迅速に完了することができる.
heap sortでは、昇順でソートする場合に最小hip、降順でソートする場合に最大hipを使用します.Heap Sortのソート手順は次のとおりです.

でソートするリストの要素でお尻を作ります.

ヒップから要素を1つずつ取り出し、アレイに順番に格納します.

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の時間的複雑さ
HeapSortはHeapソートを利用しているため,Heapの時間的複雑さには大きな関連がある.
1つの要素をheapに挿入または削除するのに要する時間の複雑さはO(log 2 n)である.また,挿入と削除が必要な要素はn個あるため,最終的な時間的複雑度はO(nlog 2 n)である.
Heap Sortの特性
Heapは最大値または最小値を容易に見つけることができるため、資料のいくつかの最大値またはいくつかの最小値を検索する際に非常に役立ちます.