4月 11, 2010

【演算】插入排序法 - Insertion Sort

@
  插入排序法(insertion sort)選擇排序法(selection sort)類似,同為較簡易、直觀的排序演算法(sorting algorithm)。其原理都是將資料分為「已排序」與「未排序」兩個部份。再將未排序資料中的第一筆資料插入到已排序資料的適當位置。



與選擇排序法相同,一般我們習慣將「已排序」的資料擺在資料序列的前端,並將「未排序」的資料擺在資料序列的後端。

若是我們需要將資料由小排到大。則我們會依序取出每個「未排序」的資料,然後由「已排序」資料的最後一筆開始,往前依序尋找第一個比這筆「未排序」資料還小的元素,並將其後的所有資料往後移一格,再將這筆「未排序」資料「插入」在這個「空出來的位子」。



其虛擬碼如下:

Function insertionSort(Type data[1..n])
    Index i, j;
    Type value;
    For i from 2 to n do
        value = data[i];

        j = i - 1;
        While j >= 1 and data[j] > value do
            data[j + 1] = data[j];
            j = j - 1;

        data[j + 1] = value;
End



讓我們看看實際操作的例子。若是我們需要將以下資料由小排到大:

83 31 96 17 42 14 54

則每一次迴圈的執行結果如下:

83 31 96 17 42 14 54

31 83 96 17 42 14 54

31 83 96 17 42 14 54

17 31 83 96 42 14 54

17 31 42 83 96 14 54

14 17 31 42 83 96 54

14 17 31 42 54 83 96



同樣的,我們必須要分析這種演算法的執行效率如何。

在資料都已排序的最佳情況下,資料大小為 n 的敘述執行次數如下:

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n - 1
            data[j + 1] = data[j];                  // 0
            j = j - 1;                              // 0

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和:B(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + (n - 1) + (n - 1) = 5n - 3 ∈ Ο(n)。複雜度為線性時間。



但是在資料完全反序的最差情況(註1):

Function insertionSort(Type data[1..n])
    Index i, j;                                     // 1
    Type value;                                     // 1
    For i from 2 to n do                            // n - 1
        value = data[i];                            // n - 1

        j = i - 1;                                  // n - 1
        While j >= 1 and data[j] > value do         // n(n - 1) / 2
            data[j + 1] = data[j];                  // n(n - 1) / 2
            j = j - 1;                              // n(n - 1) / 2

        data[j + 1] = value;                        // n - 1
End

敘述的執行次數總和:W(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n2 + 3n - 4) / 2 ∈ Ο(n2),複雜度為平方時間。

平均來說,這種演算法的執行效率並不算高,因此也比較不適合用以處理數量較多的資料。


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

4 回覆:

匿名 提到...

1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n^2 + 5n - 4)/2才對

匿名 提到...

While loop中, j >= 0 開始才對, 否則data[0]會沒有排到

匿名 提到...

while loop, j>0就好吧

匿名 提到...

請問為什麼需要j = j - 1這步驟?

張貼留言