# 高階排序演算法比較

## 測試環境

| 作業系統 | CPU | RAM |
| :--------- | :------------------------------------------------------- | :------ |
| Windows 10 | Intel(R) Core(TM) i5-1035G1 <br />CPU @ 1.00GHz 1.19 GHz | 12.0 GB |

## 資料集

### 1. 數字資料集

#### 程式碼：

void testdata(){  
    FILE *fp;
    srand(time(NULL)); //讓電腦根據時脈設定亂數種子
    fp=fopen("dataset1.txt", "w");
    for (int i=0; i<DATA_CNT; i++){
        fprintf(fp, "%d\n", rand()); //將生成出來的亂數寫入txt檔
    }
    fclose(fp);
}

### 2. 字串資料集

#### 程式碼：

void testdata(){  
    char c;
    FILE *fp;
    srand(time(NULL));
    fp=fopen("dataset2.txt", "w");
    for (int i=0; i<DATA_CNT; i++){
        for (int j=0; j<100; j++){ //每個字串長度為100
            c=rand()%52; //包含大小寫共有52個英文字元，因此對52取餘
            if (c<=25) c+='A'; //前26字母設定為大小
            else c+='a'-26; //後26個字母設為大寫
            fprintf(fp, "%c", c);
        }
        fprintf(fp, "\n"); //上面迴圈跑出100個字元後換行
    }
    fclose(fp);
}

說明：只要執行上述程式碼，就會把測資寫入dataset1.txt或dataset2.txt，或是生成那兩個txt檔。

## 排序演算法

程式碼GitHub連結：https://github.com/Darth-Phoenix/HW1-sorting

### Quick Sort

#### 1. 說明

(1)找到一個基準點(pivot)。

(2)整理陣列直到pivot左邊的元素都小於pivot，且pivot右邊的元素都大於pivot。

(3)把陣列分成pivot以左陣列以及pivot以右陣列。

(4)分別對左右兩陣列處理，即重複(1)~(3)步驟直到不可再分割。

#### 2. 圖例


#### 3. 程式碼

int partition(int *arr, int left, int right){
    int i = left; 
    int j;
    for(j = left; j < right; j++){ //把right定為pivot
        if(arr[j] <= arr[right]){ 
            swap(&arr[i], &arr[j]); //從左往右跑，遇到比pivot小的元素就從左邊往右邊疊
            i++;
        }
    }
    swap(&arr[i], &arr[right]); //全部跑完以後，i前的元素都比pivot小，所以把pivot移到i
    return i; //回傳pivot的index
}
void quicksort(int *arr, int left, int right){
    if(left < right){
        int pivot = partition(arr, left, right); //回傳後pivot左邊比較小，右邊則較大
        quicksort(arr, left, pivot-1); //對pivot以左排序
        quicksort(arr, pivot+1, right); //對pivot以右排序
    }
}

### Merge Sort

#### 1. 說明

(1)將陣列分割成很多個只有一個元素的陣列。

(2)將陣列倆倆合併，同時進行排序，合併出來的即為排序過的陣列。

(3)重複(2)的動作直到合併完成。

#### 2. 圖例


#### 3. 程式碼

void merge(int *arr, int left, int mid, int right){
    int begin_1=left,end_1=mid; //左邊陣列的邊界
    int begin_2=mid+1, end_2=right; //右邊陣列的邊界
    int k=left;//reg陣列的index，其中reg陣列為arr的暫存陣列
    while(begin_1<=end_1 && begin_2<=end_2){
        if (arr[begin_1]<=arr[begin_2]) reg[k++]=arr[begin_1++]; //兩陣列個別已排序
        else reg[k++]=arr[begin_2++]; //兩陣列同時往右邊掃描，小的值先存入reg，即完成排序
    }
    while(begin_1<=end_1) reg[k++]=arr[begin_1++];//當一陣列跑完，把另一陣列剩下元素存入 
    while(begin_2<=end_2) reg[k++]=arr[begin_2++];
    for (i=left; i<=right; i++) arr[i]=reg[i]; //把reg存回arr陣列
}
void mergesort(int *arr, int left, int right){
    if (left<right){
        int mid=(right+left)/2;
        mergesort(arr, left, mid); //對mid左邊分割
        mergesort(arr, mid+1, right); //對mid右邊分割
        merge(arr, left, mid, right); //倆倆合併
    }
}

### Heap Sort

#### 1. Max Heap

轉成Tree的型態，每個節點(Node)都會比它的子節點(ChildNode)大，即為Max Heap型態。


#### 2. 說明

(1)將陣列轉為Max Heap資料(Heapify)。

(2)樹的root即為最大值，把root跟未排序的最後一項互換。

(3)對剩下未排序的陣列再進行heapify。

(4)重複(2)、(3)步驟直到陣列排序完成。

#### 3. 圖例


#### 4. 程式碼

void heapify(int *arr, int n, int i){ 
    int c1=2*i+1; //Left Child
    int c2=2*i+2; //Right Child
    int max=i; //找指定節點跟它的子節點中最大的值
    if (c1<n && arr[c1]>arr[max]) max=c1;
    if (c2<n && arr[c2]>arr[max]) max=c2;
    if (max!=i){ //如果Parent Node不是最大的
        swap(arr, max, i); //把最大值換到上面
        heapify(arr, n, max); //交換後子節點未必符合Max Heap，因此換下來的節點再heapify
    }
}
void heapsort(int *arr, int n){
    for (int i=n/2-1; i>=0; i--){
        heapify(arr, n, i);//從下往上對所有父節點進行Heapify，完成後即形成Max Heap
    }
    for (int i=n-1; i>=0; i--){
        swap(arr, i, 0); //此時樹根為最大值，樹根的index為0，把它換到最後面形成sorted部分
        heapify(arr i, 0); //對樹根heapify，因為交換後樹根不一定符合Max Heap
    }
}

### Radix Sort

#### 1. 說明

(1)將陣列分成很多個位數進行比較，從第一個位數開始。

(1)每個位數先利用counting sort做出一個count一維陣列。

(2)原陣列從後往前根據count陣列插入相對應的位置。

(3)對下一個位數重複(1)、(2)動作直到跑完所有位數即完成排序。

#### 2. Counting Sort


Radix Sort的作法即為由小到大對每個位數做Counting Sort。

#### 3. 程式碼

void radixsort(int *arr, int n){
    int exp=1;
    for (int i=1; i<=10; i++){ //integer範圍最多10個位數，故跑10次迴圈
        int count[10]={0}; //每個位數包含0~9，故大小為10
        for (int j=0; j<n; j++){
            count[(arr[j]/exp)%10]++; //計算exp對應到的位數的每個數字出現次數
        }
        for (int j=1; j<10; j++){
            count[j]+=count[j-1]; //調整成陣列每個元素要放入的index
        }
        for (int j=n-1; j>=0; j--){
            output[count[(arr[j]/exp)%10]-1]=arr[j]; //output存入count陣列的索引值
            count[(arr[j]/exp)%10]--; //下次要存入output陣會存到前一格        
        }
        exp*=10; //這個位數做完乘10換下個位數
        for (int j=0; j<n; j++){
            arr[j]=output[j]; //把調整過的陣列複製回原本的陣列
        }
    }
}

## 實作結果

### 1. 執行時間

| | 1000000組integer | 1000000組長度為100的string |
| --------- | ---------------- | -------------------------- |
| QuickSort | 0.169386 sec | 0.415781 sec |
| MergeSort | 0.193767 sec | 0.447222 sec |
| HeapSort | 0.311839 sec | 1.115715 sec |
| RadixSort | 0.132293 sec | 6.946972 sec |

### 2. 時間複雜度

| | QuickSort | MergeSort | HeapSort | RadixSort |
| :----------- | --------- | --------- | -------- | --------- |
| Best Case | O(nlogn) | O(nlogn) | O(nlogn) | O(d*n) |
| Worst Case | O(n²) | O(nlogn) | O(nlogn) | O(d*n) |
| Average Case | O(nlogn) | O(nlogn) | O(nlogn) | O(d*n) |

#### 說明:

(1) QuickSort的Worst Case發生在測資本來就是排序完或相反的情況，每次挑選pivot都是選到最大或最小的，造成呼叫遞迴次數較多。

(2) RadixSort的時間複雜度O(d*n)中，d為最多位數數量，也表示此排序法要跑d次迴圈。

### 3. 空間複雜度

| | QuickSort | MergeSort | HeapSort | RadixSort |
| ---------------------- | --------- | --------- | -------- | --------- |
| Worst Space Complexity | O(n) | O(n) | O(1) | O(n+d) |

#### 說明：

(1) QuickSort會根據呼叫遞迴的次數決定額外使用的空間量，最多會用到額外空間O(n)。

(2) MergeSort會開一個大小為n的陣列用來暫存，空間複雜度為O(n)。

(3) RadixSort的空間複雜度O(n+d)中，d為一個位數中可能的值的數量，也就是count陣列的大小，而n為一個大小為n的陣列用來暫存。

### 4.穩定性

| | QuickSort | MergeSort | HeapSort | RadixSort |
| --------- | --------- | --------- | -------- | --------- |
| Stability | 不穩定 | 穩定 | 不穩定 | 穩定 |

#### 說明：

(1)QuickSort、HeapSort在swap的過程皆可能使相同的鍵值先後順序顛倒。

(2)MergeSort在合併的過程中比較時如果鍵值相同會優先放入左邊的陣列，使得先後順序維持一樣。

(3)RadixSort在根據count陣列插入暫存陣列的過程時，是陣列由後往前判斷，且同一個位數的數值是由後往前放，因此先後順序不會改變。

## 總結

1. QuickSort處理數字第二快、處理字串最快，但在少數情況可能因為測資不同而比較慢，例如如果在Worst Case情況呼叫遞迴的次數較多，造成時間複雜度變為O(n²)。
2. MergeSort大致上跟QuickSort差不多快，因為是採用類似方式呼叫遞迴，但MergeSort最大的缺點就是必須使用較多的記憶體空間。
3. HeapSort的速度比前兩個排序法慢了一小截，但用的額外記憶體是這些排序法中最少的。
4. RadixSort的處理數字速度最快，處理字串卻比其他排序法慢一大截。主要的原因是跟測資的位數有關，在我們實作的測資中，隨機出來的integer範圍最多10位數，而字串卻是100位數，顯得Radix在排序字串會慢很多。因此，如果測資是long long，排序數字就會跑更慢，相對地如果字串的長度變比較短，排序字串就會變得比較快。

## 參考資料

https://www.geeksforgeeks.org/quick-sort/

https://www.interviewbit.com/tutorial/merge-sort-algorithm/

https://www.youtube.com/watch?v=j-DqQcNPGbE&t=6s

https://www.geeksforgeeks.org/radix-sort/

https://rust-algo.club/sorting/radix_sort/

http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php

http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm

https://medium.com/@info.gildacademy/time-and-space-complexity-of-data-structure-and-sorting-algorithms-588a57edf495#:~:text=Space%20complexity%20is%20a%20function,the%20number%20of%20items%20processed

https://magiclen.org/sorting-algorithm/

https://www.geeksforgeeks.org/analysis-of-different-sorting-techniques/