Table of Contents
前言
一連講了五天的背景知識，今天我們終於要來開始上主菜了，而主菜也是有很多的類別：
- Brute Force
- Decrease and Conquer
- Divide and Conquer
- Transform and Conquer
- Time and Space Tradeoffs
- Dynamic Programming
- Greedy Techniques
在我們這30天的系列中，我們也會針對這七個類別中一些比較基礎的演算法進行介紹，今天的主題是Brute Force中的Selection Sort。
什麼是Brute Force？
Brute Force就是針對要解決的問題，用最『直接』的方始去取得結果，我個人覺得最簡單的說法就是暴力破解，例如要計算某個數值X的n次方，那就真的去把X乘n次、或者是要從一堆資料中找出某一筆資料，就把這堆資料中每一個資料都拿出來比對。那可能會有人覺得：『既然是暴力破解法，那Brute Force沒什麼特別的啊，幹嘛要特別說？！』，至少我曾經這麼想過，但是我覺得就是因為Brute Force沒什麼特別的，所以我自己認為他是演算法的『源頭』，藉由了解最原始的做法，才能知道未來演變出的演算法的優勢及好處。
Selection Sort如何運作？
其實要了解一個演算法，透過 排序(Sort)及搜尋(Search) 大概會是最容易的方式了，今天我們就來介紹第一個屬於Brute Force的演算法–Selection Sort，既然名字都已經有Sort了，自然表示這個演算法的目的是用在排序，基本上這個演算法的步驟為下：
- 針對整個數列進行搜尋，尋找
最小的值，然後把這個最小的值換到第一個位置。 - 再
從第二個數值位置開始搜尋整個數列，一樣尋找最小的值，然後把這次找到的最小的值換到第二個位置。 - 重複上述動作，直到最後一個數值。
對，這個Selection sort就是這麼的簡單，沒有複雜的流程，沒有複雜的理論，非常簡顯易懂，那Pseudo-code則是下面這樣：
// Input: An array Array[0...n-1] of orderable elements
// Output: An array Array[0...n-1] sorted in ascending order
function SelectionSort(Array[0, ..., n-1]){
for i = 0 to n-2 {
min = i
for j = i + 1 to n-1 {
if Array[j] < Array[min]{
min = j
}
}
SWAP Array[i] and Array[min]
}
}
Selection Sort的時間複雜度(Time complexity)
在講Selection Sort的時間複雜度之前，我們先透過一張GIF來『視覺化』Selection Sort的步驟吧。
從上面的GIF可以看到，短短一個長度為8的陣列，在進行Selection Sort的時候，就會需要進行數值大小比較28次和數值交換7次，也就是說，透過Selection Sort每跑一次長度為n的陣列，就需要進行接近n^2/2次的數值比較和n-1次的數值交換，另外，從Pseudo-code中可以看到跑一次Selection Sort會跑兩次執行時間決定於n的大小的巢狀迴圈，因此其時間複雜度為𝜪(n^2)；而對於Selection Sort而言，Best Case、Average Case和Worst Case的時間複雜度都是𝜪(n^2)。
為什麼要使用Selection Sort?
- Selection Sort執行的時候，讀取數據(writes)次數為
𝜪(n^2)，而寫入數據(reads)次數為𝜪(n)。 - 當寫入的動作的『費用』比讀取的動作來的高出許多時，那Selection Sort就會是一個比較好的選擇。
- 如果要處理的陣列是個長度很小的陣列，那Selection Sort就相對有效率，而且比較容易實現。
小結
- Brute Force其實就是暴力破解法。
- Selection Sort是從中尋找最小的值後與最前面的數值交換位置，直到整個數列變成從小到大的排序。
- Selection Sort的時間複雜度為𝜪(n^2)。
預告
明天我們將會介紹第二個屬於Brute Force的演算法-Bubble Sort。