# 高階排序演算法比較
## 測試環境
| 作業系統 | CPU | RAM |
| :--------- | :------------------------------------------------------- | :------ |
| Windows 10 | Intel(R) Core(TM) i5-1035G1 <br />CPU @ 1.00GHz 1.19 GHz | 12.0 GB |
## 資料集
### 1. 數字資料集
#### 程式碼:
```c
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. 字串資料集
#### 程式碼:
```c
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. 圖例
![](https://i.imgur.com/bQOQ7jP.png =500x)
#### 3. 程式碼
```c
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. 圖例
![](https://i.imgur.com/UUFBB7m.png =500x)
#### 3. 程式碼
``` c
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型態。
![](https://i.imgur.com/rnufV2P.png =500x)
#### 2. 說明
(1)將陣列轉為Max Heap資料(Heapify)。
(2)樹的root即為最大值,把root跟未排序的最後一項互換。
(3)對剩下未排序的陣列再進行heapify。
(4)重複(2)、(3)步驟直到陣列排序完成。
#### 3. 圖例
![](https://i.imgur.com/sCcpQ5S.png =500x)
#### 4. 程式碼
``` c
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
![](https://i.imgur.com/TKHqITd.png)
Radix Sort的作法即為由小到大對每個位數做Counting Sort。
#### 3. 程式碼
``` c
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/