作者 江柏翰、吳奕勳 / 康橋國際學校國中部
一、研究動機
書，不管在什麼地方，都是個不可或缺的存在。就好比哈利波特裡的霍格華茲圖書館，有著成千上萬的書供那裡的師生閱覽。然而，這麼多的師生每天借閱這些書，圖書管理員厄瑪·平斯究竟該如何在他們還書後將這些書依序排好呢?
二、研究目標
我們希望能透過比較三種排序方法的耗時，找出能讓我們在最短時間來將雜亂的書依序排好的排序演算法(sorting algorithm)，並比較每種演算法的最長耗時時間及平均耗時時間。
三、研究方法
- 研究內容簡介
排序演算法主要用來排序陣列裡的元素。不同的排序演算法都有各自的演算方式，進而使在排序上花費的時間有所差異。我們將以時間複雜度來分析氣泡排序法(bubble sort)，合併排序法(merge sort)，及桶排序法(bucket sort)。 - 了解時間複雜度及bio O
a. 分析演算法的指標
評斷一個演算法好壞最基本的兩個指標，是演算法運行所需的時間(時間複雜度)及其所將會用到的記憶體(空間複雜度)，而用來記錄這二者的符號便是大O符號(Big O Notation)。
b. 時間複雜度及Big O符號定義
時間複雜度是一個函數，描述一個演算法運行所需的時間。
而Big O/大O符號，又稱為漸進符號，則是一種數學符號，描述了函式輸入資料量趨近無窮大時的漸進行為，進而被用來記錄演算法的複雜度。以下為其數學定義：T(n) 和 f(n) 為兩個正函數，T(n)為演算法執行時間。為若T(n) ∊ O(f(n))，及如有常數M 和 n₀那所有n ≥ n₀的值都適用T(n) ≤ M·f(n)。
(圖一: T(n)和f(n)的成長速度[1])
*T(n) ∊ O (f(n)) 代表T(n)不會比 f(n)增長得快[1]。
此外，在計算一個演算法的大O時，只會保留增長最快的項。舉例來說，一函式f(x) = 4x4 - 2x + 5。當x接近無窮大時，4x4 值將遠遠大於其他項，其他項的值也將微不足道。因此，在計算時只保留增長最快的項(4x4 )。
c. 常見的big O例子
i. O(1)：
定義：輸入不會影響所需的執行步驟(時間) / 不管輸入是甚麼都只需要常數個步驟
ii. O(n)：
定義: 執行時間(/步驟)會隨著輸入等比例增加。
3. 解釋三個排序演算法:
在這次的研究中，我們選了三個較為常見的排序演算法來比較。我們所挑選的演算法為氣泡排序法(bubble sort)、合併排序法(merge sort)、及桶排序法(bucket sort)。
a. 氣泡排序法步驟：
i. 比較由輸入資料所組成的陣列的第一、二個位置的數字。
ii.如果在比較時位於左邊的數字比較大，則與右邊的數互換位置。
iii.完成i.、ii.後，比較的位置各往右移一格（舉例來說，第一次比較一定是比較位置一跟二的數字，而在第二步後下一次要比較的位置就會各加一，也就是比較位置二跟位置三，以此類推）。
iv.重複步驟i.-iii. 直到最後一個位置也已經與前一個位置進行比較。
v.重複步驟i.-iv. n(輸入的資料數/陣列的資料數)次。
vi.以陣列[2,5,1,4,3]來演示泡沫排序法的流程:
b. 合併排序法步驟:
i. 將由輸入的n筆資料組成的陣列分成兩個陣列（各擁有一半的資料）。
*如資料數為奇數，則在分陣列時給左邊新分出來的陣列多一個數。只擁有一個資料/數的陣列將不再進行分裂，但在合併時與其他陣列一樣正常合併。
ii. 重複步驟i.直到所分出來的陣列數(不與最後一次分陣列前的陣列數疊加)等於n。
iii. 兩兩一組，從最左邊的陣列開始，與其右邊的陣列合併(舉例來說陣列一和二合併，三和四合併)。合併時需依由小到大的順序把數字放入新的陣列。
iv. 重複步驟iii.直到只剩一個陣列，該陣列即為排序完的結果。
v.以陣列[2 , 6 , 5, 1, 7, 4, 3] 來演示合併排序法的流程:
c. 桶排序法步驟:
i.將原本的陣列分成若干個陣列，每個小陣列都只能含有一定範圍的數字，且範圍不重複(舉例來說:1 ~ 7 & 8 ~ 14)。小陣列數及陣列裡數字的範圍都是自己訂。
ii.將小陣列內的資料從小到大排序
iii.將小陣列個陣列進行合併
*盡量讓所有小陣列裡的資料數相同。
4. 分析三個演算法的時間複雜度
a. 氣泡排序法的時間複雜度分析：
i. 平均、最壞時間複雜度：
氣泡排序法的平均時間複雜度是O(n2)。這是因為其會需要兩個指標來作比較。在程式語言中要用到兩個指標來作比較，就會需要用到雙重for迴圈。雙重for迴圈就是在一個for迴圈裡再執行一個for迴圈。For迴圈將執行n次，而在這個for迴圈裡又執行n次的話，總共便需執行n2次，故泡沫排序法的平均時間複雜度是O(n2)。而氣泡排序法的平均與最壞時間複雜度是一樣的因為不管在什麼情況氣泡排序法都會用到兩個指標，所以時間複雜度不會改變。
b. 合併排序法的時間複雜度分析：
i. 平均、最壞時間複雜度：
合併排序法大致分為兩個部分：分陣列及合併陣列。分陣列的執行步驟為log(n)，因為每次都是以一半來做分成更多的陣列，所以你所花的時間才會是log(n)。而合併陣列的執行步驟則是為O(n) ，因為在合併時只需用到一個for迴圈。在計算時間複雜度時只會保留增長最快的項，nlog(n) > log(n)，故合併排序法的時間複雜度為O(nlog(n))。合併排序法的平均及最壞時間複雜度是一樣的因為只要資料數相同，此排序法都會執行一樣的分級合併陣列的動作，故平均與最壞時間複雜度是一樣的。
c. 桶排序的時間複雜度分析：
i. 平均、最壞時間複雜度：
桶排序的平均時間複雜度是O(n)，因為桶排序不是使用比較的手法來排序，是屬於線性、分配式的排序。因此只需常數個執行步驟。而桶排序的平均及最壞時間複雜度是一樣的，因為桶排序法不管在甚麼情況都會把原本的陣列分成好幾個，固平均與最壞時間複雜度相同。
四、研究結果
下表格為三個演算法的時間複雜度比較：
| 演算法 | 平均時間複雜度 | 最差時間複雜度 |
| 氣泡排序法 | O(n2) | O(n2) |
| 合併排序法 | O(nlog(n)) | O(nlog(n)) |
| 桶排序法 | O(n) | O(n) |
- 比較三個演算法的時間複雜度
決定演算法的好壞通常會看最壞時間複雜度。透過上表格，我們可以得知時間複雜度最小的排序演算法為桶排序法，緊接著是合併排序法，最後則是氣泡排序法。因此，我們斷定在我們探討的三個排序法中，桶排序法最能使厄瑪·平斯最快將圖書館凌亂的書依序排好。
五、結語:
透過必較不同時間複雜度，我們得以找出效率最高的排序演算法：桶排序法，進而幫助厄瑪·平斯以最短的時間排序完雜亂的書。但是，面對成千上萬的書要排，就算有了演算法的幫助，要排完這些書，厄瑪·平斯大概也得花上好幾天吧。
六、參考資料:
[1]: Nilsson, S. (n.d.). Big O notation: Definition and examples. · YourBasic. Retrieved February 14, 2022, from https://yourbasic.org/algorithms/big-o-notation-explained/