資料結構DS_HW01

緣起:

    我們的資料結構有個功課，要我們繳一份跟排序演算法有關的報告，跟以往單純寫程式的題目有些不同，不只要寫程式，還要分析它的效能，然後解譯。

    這題目花了我不少時間，也可以算是一個小專題了，所以，我想把我的報告 PO 上來，記錄下。

題目:

程式碼:

github

我的報告:

資料結構-H01、陳贊旭、1074541

前言:

我的程式能測量 Selection Sort 在3 種情況下分別花的平均時間 (100次的平均)，還有swap(交換資料)函數使用的次數。

在電腦正常運作情況下

已排序資料 : 0.1358 秒

逆排序資料 : 0.1500 秒

完全隨機資料 : 0.1373 秒

在包含命令提式字元的安全模式下

已排序資料 : 0.2256 秒

逆排序資料 : 0.2514 秒

完全隨機資料 : 0.2301 秒

結果就是，逆排序資料花費時間 > 完全隨機資料花費時間 > 已排序資料花費時間

系統架構:

副程式說明:

swap : 接收兩個整數，進行交換。

postiveRank : 接收一個大小為10000的陣列，將1~10000依序存入陣列裡。(39~44行)

negativeRank : 接收一個大小為10000的陣列，將10000~1依序存入陣列裡。(32~37行)

randomRank : 接收一個大小為10000的陣列，將1~10000隨機存入陣列裡(不重覆數字)。(46~77行)

selectSort : 接收一個大小為10000的陣列，並將它做由小到大的排序。(17~30行)

duplicateCheck : 接收一個大小為10000的陣列，如果陣列裡的數字(1~10000)有重覆的話，它會輸出 “yes” ，否則輸出 “no”。(79~90行)

printArr : 接收一個大小為10000的陣列，將陣列裡的資料依序印出。(92~95行)

成果說明一:

在產生亂數前，先使用 srand() 來設定亂數種子，裡面傳入的值是一直變動的時間(50行)，使每次產生的亂數夠亂，不過，還是不能確保不會出現相同的數字，所以，直接把產生的亂數存進陣列裡，顯然不是一個產生隨機排序陣列的好方法，我是使用串列來解決這問題。

首先，產生一個有10000筆資料(1,2,3…10000)的串列(52~57行)，變數 i 控制抽取次數，同時也代表串列的大小(59行)，之後把 rand() 產生的數字拿來 % i ，得到的結果用以限制第二層迴圈的執行次數(63行)，確保在遊歷串列的資料時(63~66行)，不會超出串列目前的大小，得不到數字。

跑完迴圈後，trave 會指到串列的第 rand()%i+1筆資料，再把trave所指位置的值依序存進陣列裡(67行)，最後，在串列裡刪除trave所指的元素，並釋放記憶體(68~75行)。

以下用簡化的圖來說明。

每種 Case，我都讓它們跑了100次，單Case3來說，總共會產生100個隨機排序的陣列。基本上，在那100筆大小10000的陣列中，某兩筆資料完全相同的可能性太低了(1/10000!)，而且，資料量也很小(才100筆)，所以，每一輪應該都是不同的資料。

成果說明二:

如何完成測量:

我利用time函式，在進入排序的程式前，先記錄下時間(106,115,124行)，然後等排序的程式跑完，記錄時間差(毫秒)的加總(108,117,126行)，重覆100次，最後輸出時間差的加總/100(110,119,128行)。

我讓程式在兩種情況下跑，第一種是正常情況，我只開著Dev-C (有很多背景程式沒有關掉)，直接按F11編譯執行。第二種情況是，進入windows的安全模式，使用命令提式字元來執行編譯好的exe檔。

測量的結果是以在安全模式下執行的為準，根據Microsoft的說明頁上寫的，"安全模式是Windows的疑難排解選項，能夠以最低限度的狀態啟動您的電腦"。

因為電腦只執行必要的程式，所以CPU在程式間的切換頻率就會比正常情形況還要少，因此，測出來的相對時間，會比較可信。

雖然在安全模式下，程式花的時間都比一般模式還要長，不過，這兩種模式所得到的最終結果都是  逆排序資料花費時間 > 完全隨機資料花費時間 > 已排序資料花費時間。

不同資料類形，效能的差異:

資料類形的不同，的確會讓排序程式有執行時間上的差異。已排序的資料，平均花的時間最少，而逆排序的資料，平均花的時間最多，滿合情合理的。

從演算法的角度來說明原因:

觀察我們的selectSotr函式，我們會發現，不管資料是怎麼排序的，第一個 for 迴圈裡的 swap 函式，固定都會執行 9999 次，所以，swap函式就不列入影響了。資料排序也不會影響到第二個迴圈的執行，它的執行次數也是固定的，判斷式也是，所以，現在唯一會造成程式快慢的因素，就是第二層迴圈裡，條件判斷式成立後，min = j 的動作次數。

正排序的資料 : 左邊的資料永遠會小於右邊的資料，所以，陣列裡第 i 個資料的值，永遠會小於陣列裡第 j 個資料的值。selectSort 跑完後， min=j; 這行程式執行的次數會是 0 。

逆排序的資料 : 左邊的資料都會大於右邊的資料，所以，外迴圈跑第一次下來， min=j 會執行 9999 次，接下來，外層的 for 迴圈每再執行一次， min=j 都會執行 9999-2N 次 (N  = 外層迴圈執行次數 - 1)，直到 i=5000。selectSort跑完後， min=j; 這行程式的執行次數會是 9999+9997+9995+…..+1次。

隨機排序的資料 : 這個我就不確定了，不過 min=j; 的執行次數應該會落在正排序跟逆排序之間。

我額外寫了一個程式，單獨把 randomRank、postiveRank、negativeRank、selectSort，拿出來，並在selectSort裡加了一個變數叫 count，初始值為0，只要程式有執行到 min=j; 那行，count就會加1，最後，selectSort執行完後，會把count印出來。

以下是執行結果，由上到下分別是，正排序、逆排序、完全隨機排序。