本系列文章同步分享於個人Blog → Informistry-HankLee

前言

一連講了五天的背景知識，今天我們終於要來開始上主菜了，而主菜也是有很多的類別：

1. Brute Force
2. Decrease and Conquer
3. Divide and Conquer
4. Transform and Conquer
5. Time and Space Tradeoffs
6. Dynamic Programming
7. 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了，自然表示這個演算法的目的是用在排序，基本上這個演算法的步驟為下：

1. 針對整個數列進行搜尋，尋找最小的值，然後把這個最小的值換到第一個位置。
2. 再從第二個數值位置開始搜尋整個數列，一樣尋找最小的值，然後把這次找到的最小的值換到第二個位置。
3. 重複上述動作，直到最後一個數值。

對，這個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 do:
        min = i
        for j = i + 1 to n-1 do:
            if Array[j] < Array[min]:
                min = j
            end if
        end for
        SWAP Array[i] and Array[min]
    end for
}

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?

1. Selection Sort執行的時候，讀取數據(writes)次數為Ｏ(n^2)，而寫入數據(reads)次數為Ｏ(n)。
2. 當寫入的動作的『費用』比讀取的動作來的高出許多時，那Selection Sort就會是一個比較好的選擇。
3. 如果要處理的陣列是個長度很小的陣列，那Selection Sort就相對有效率，而且比較容易實現。

小結

• Brute Force其實就是暴力破解法。
• Selection Sort是從中尋找最小的值後與最前面的數值交換位置，直到整個數列變成從小到大的排序。
• Selection Sort的時間複雜度為Ｏ(n^2)。

預告

明天我們將會介紹第二個屬於Brute Force的演算法-Bubble Sort。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin