# 簡單排序演算法比較
## 測試環境
| 作業系統 | CPU | RAM |
| :--------- | :------------------------------------------------------- | :------ |
| Windows 10 | Intel(R) Core(TM) i5-1035G1 <br />CPU @ 1.00GHz 1.19 GHz | 12.0 GB |
## 排序演算法
### Bubble Sort
#### 1.說明
(1)比較相鄰的兩個元素，若前面的元素較大就進行交換。
(2)重複進行(1)的動作直到最後面，最後一個元素將會是最大值。
(3)重複進行(1),(2)的動作，每次比較到上一輪的最後一個元素。
(4)重複進行以上動作直到沒有元素需要比較。
#### 2.圖例
#### 3.程式碼
```c
void bubble_sort(int a[], int len){
int i, j, temp;
for (i=0; i<len-1; i++) {
for (j=0; j<len-1-i; j++)
if (a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
```
### Selection Sort
#### 1.說明
(1)從未排序的數列中找到最小的元素。
(2)將此元素取出並加入到已排序數列最後。
(3)重複以上動作直到未排序數列全部處理完成。
#### 2.圖例
#### 3.程式碼
``` c
void selection_sort(int a[],int len){
int temp, minIdx;
int i, j;
for (i=0; i<len-1; i++){
minIdx=i;
for (j=i+1; j<len; j++){
if (a[j] < a[minIdx])
minIdx=j;
}
temp=a[minIdx];
a[minIdx]=a[i];
a[i]=temp;
}
}
```
### Insertion Sort
#### 1.說明
(1)從未排序數列取出一元素。
(2)由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。
(3)重複以上動作直到未排序數列全部處理完成。
#### 2.圖例
#### 3.程式碼
``` c
void insertion_sort(int a[], int len){
int i, j, key;
for (i=1; i<len; i++) {
j=i;
key=a[i];
while (j>0 && a[j-1]>key) {
a[j]=a[j-1];
j--;
}
a[j]=key;
}
}
```
## 測試資料
### 建立Data方法及數量
#### 1.說明
(1)於開頭先設定資料大小為1000000
(2)以rand()產生隨機整數
(3)以srand()設定亂數種子，使亂數的數值及序列固定
(4)以迴圈執行將資料存入陣列
#### 2.程式碼
``` c
#include <stdio.h>
#include <stdlib.h>
#define DATA_CNT 100000
int main(){
int num[DATA_CNT+5];
int i;
srand(1);
for (i=0; i<DATA_CNT; i++){
num[i]=rand();
printf("%d ", num[i]);
}
return 0;
}
```
### 將測資存入文件
如下圖，桌面上有名為testdata.c的程式碼檔案，以及編譯出來名為testdata.exe的執行檔
接著，進入cmd(命令提示字元)，先cd到存入以上檔案的位置
最後，輸入以下指令，檔案位置將會產生所需的測資文字檔
testdata.txt即為測資文字檔
## 測量效能
### 1.gettimeofday()
#### (1)函數原型
\#include <sys/time.h>
int gettimeofday(struct timeval*tv,struct timezone *tz )
#### (2)說明
gettimeofday()會把目前的時間用tv 結構回傳，當地時區的訊息則放到tz所指的結構中
#### (3)資料結構
timeval
```c
struct timeval{
long tv_sec; //秒
long tv_usec; //微妙
}
```
timezone
```c
struct timezone{
int tz_minuteswest; //和greenwich 時間差了多少分鐘
int tz_dsttime; //type of DST correction
}
```
在gettimeofday()函數中tv或者tz都可以為空。如果為空則就不回傳其對應的結構。
### 2.計算時間差方式
(1)於程式開頭定義兩個timeval，方別為start以及end
(2)於進入sort_function()前紀錄一次start的時間
(3)於執行完sort_function()後紀錄一次end的時間
(4)end.tv_sec - start.tv_sec即為兩個時間的"秒數"差(結果為一整數)
(5)end.tv_usec - start.tv_usec即為兩個時間的"微秒數"差
(6)可以利用兩者單位換算相加即為start及end的時間差
### 3.程式碼
``` c
#include <stdio.h>
#include <stdlib.h>
#define DATA_CNT 100000
int main(){
int num[DATA_CNT+5];
int i;
struct timeval start;
struct timeval end;
unsigned long timer;
srand(1);
for (i=0; i<DATA_CNT; i++){
num[i]=rand();
}
gettimeofday(&start, NULL);
sort_function(num,DATA_CNT);
gettimeofday(&end, NULL);
timer = 1000000*(end.tv_sec-start.tv_sec) + end.tv_usec - start.tv_usec;
printf("Sorting performance %ld us (equal %f sec)\n", timer, timer / 1000000.0);
return 0;
}
```
## 實驗結果
| 項目 | Bubble Sort | Selection Sort | Insertion Sort |
| ----------------- | ------------- | -------------- | -------------- |
| 效能(Performance) | 29.875098 sec | 12.535177 sec | 6.721281 sec |
| 穩定性(Stability) | Stable | Unstable | Stable |
(如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序。反之則為不穩定排序)
### 時間複雜度
| | Bubble Sort | Selection Sort | Insertion Sort |
| ------------ | ----------- | -------------- | -------------- |
| Best Case | O(n) | O(n²) | O(n) |
| Worst Case | O(n²) | O(n²) | O(n²) |
| Average Case | O(n²) | O(n²) | O(n²) |
### 空間複雜度
| | Bubble Sort | Selection Sort | Insertion Sort |
| ---------------- | ----------- | -------------- | -------------- |
| Space complexity | O(1) | O(1) | O(1) |
## 結論
1. Bubble Sort只適合處理小型資料，原因是在排序過程中，需要經過非常多次的判斷以及交換，是三種排序法中最沒效率的排序法。
2. 在一般的情況中，Selection Sort交換次數較Bubble Sort少非常多，因此效能比Bubble Sort高非常多。
3. Selection Sort之所以為Unstable的原因是在排序完後，鍵值相同的兩個值先後順序可能換互換。ex: 在i=0時，陣列的值為
5 8 9 5 4 1，因為最小值為1，陣列中第一個5將會與1的位置互換，使得兩個5的前後順序交換。
4. Insertion Sort的判斷次數為三種排序法之中最少的，交換次數也不多，因此為三種排序法中最有效率的排序法。
5. 效能: Insertion Sort > Selection Sort > Bubble Sort
#### 參考資料
https://techdemic.com/bubble-sort/
https://studyalgorithms.com/array/selection-sort/
https://www.geeksforgeeks.org/insertion-sort/
https://www.geeksforgeeks.org/selection-sort/
https://www.geeksforgeeks.org/bubble-sort/
https://emn178.pixnet.net/blog/post/93915544
https://emn178.pixnet.net/blog/post/93779892
https://emn178.pixnet.net/blog/post/93791164
https://nosleep.pixnet.net/blog/post/205120138-%E7%A8%8B%E5%BC%8F%E9%96%8B%E7%99%BC-%7C-%5Blinux%5D%5Bc%5D-%E4%BD%BF%E7%94%A8-gettimeofday%28%29-%E5%87%BD%E5%BC%8F%E8%A8%88%E7%AE%97
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php
https://www.geeksforgeeks.org/analysis-of-different-sorting-techniques/
http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm
Sign in with Wallet
Connect another wallet