3月 20, 2010

【演算】選擇排序法 - Selection Sort

@
  選擇排序法(selection sort)為一種較直觀的排序演算法(sorting algorithm)。其將資料分為「已排序」與「未排序」兩部份,並從「未排序」的資料中找出最大(最小)值,放入「已排序」資料的最後端。如是進行,直到排序結束(未排序資料為空)為止。



  一般來說,我們的作法是:將「已排序」的資料擺在資料序列的前端,並將「未排序」的資料擺在資料序列的後端。

  假設我們需要將 n 筆資料由大排到小。在起初,這 n 筆資料都是「未排序」的。於是,我們從這 n 筆資料取出其中的最大值,並將之放在「已排序」資料的最後端。換言之,就是將之與第一筆資料進行交換。

  接著,我們再從剩下的 n - 1 筆資料取出最大值,同樣放入「已排序」資料的最後端(與第二筆資料進行交換);再從剩下的 n - 2 筆資料取出最大值,放入「已排序」資料的最後端(與第三筆資料進行交換)。

  以此類推,直到沒有任何「未排序」的資料為止。



  選擇排序法的虛擬碼大致如下:

Function selectionSort(Type data[1..n])
    Index i, j, max
    For i from 1 to n do
        max = i
        For j from i + 1 to n do
            If data[j] > data[max] then
                max = j

        Exchange data[i] and data[max]
End



  舉例來說,若我們需要將以下資料由大排到小:

19 58 33 41 28 14 53 84

  則以此演算法運作的過程如下:

84 58 33 41 28 14 53 19
84 58 33 41 28 14 53 19
84 58 53 41 28 14 33 19
84 58 53 41 28 14 33 19
84 58 53 41 33 14 28 19
84 58 53 41 33 28 14 19
84 58 53 41 33 28 19 14
84 58 53 41 33 28 19 14



  若是我們分析在最差情況下(所有資料的順序剛好完全相反),使用選擇排序法將 n 筆資料排序的敘述執行次數(註1):

Function selectionSort(Type data[1..n])
    Index i, j, max                                 // 1
    For i from 1 to n do                            // n
        max = i                                     // n
        For j from i + 1 to n do                    // n(n - 1) / 2
            If data[j] > data[max] then             // n(n - 1) / 2
                max = j                             // n(n - 1) / 2

        Exchange data[i] and data[max]              // n
End



  經由以上,我們可以得到最差情況下,敘訴的執行次數總和:W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n2 + 3n - 2) / 2 ∈ Ο(n2)。

  由此可知,選擇排序法的時間複雜度與之前介紹過的氣泡排序法(bubble sort)相當,同樣為效率不大優良的排序演算法。


註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。

5 回覆:

匿名 提到...

W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n2 + n - 2) / 2 ∈ Ο(n2)。

請問一下下,這是怎麼算出來的? 看不懂><"

Unknown 提到...

這是由上面虛擬碼的執行次數(// 註解後的數字)加總得來的。
可以參考:
http://program-lover.blogspot.com/2008/10/complexity-analysis.html

不過其實我加錯了,漏加了 Exchange 執行次數的 n :P

匿名 提到...

本來數字是33,後來變成53?
請問是不是過程錯了?

匿名 提到...

哦…對不起,是我看錯了。

匿名 提到...

W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n2 + 3n - 2) / 2
帶N進去算,兩邊的答案會不相等...

(3n2 + 3n - 2) / 2
好像有點問題...
如果改成
(3n2 + 3n + 2) / 2
我帶N進去算答案會是相等的

張貼留言