2015年8月9日 星期日

Insertion Sort

Insertion Sort 的作法應該是一般人直覺最容易想到的排序方法,像是給你一副亂掉的撲克牌要你從小排到大,先假設只有一種花色,例如說梅花好了。一般人可能會直接想到把牌理好展開(不管是在手上或在桌上),然後先找梅花 A,把它放在最左邊(或者獨立出來一排),然後再找梅花二,放在梅花 A 的旁邊,再找梅花三,放在梅花二旁邊,依此類推,從小到大去找牌,並且往左邊放。

舉例,假設一開始亂掉的十三張梅花牌,理好展開長這樣:
Q 9 K 5 3 A 8 2 6 4 7 10 J

第一個先找 A,放到最左邊:
Q 9 K 5 3 A 8 2 6 4 7 10 J
=>
A Q 9 K 5 3 8 2 6 4 7 10 J

然後找 2,放到 A 的旁邊,因為 A 已經固定了,所以我們眼光只要從 Q 以後開始去掃描就好:
A Q 9 K 5 3 8 2 6 4 7 10 J
  ^從這裡以後往右去找
=>
A 2 Q 9 K 5 3 8 6 4 7 10 J
^^^從頭到這裡已經排好了

再來是 3,因為 A 和 2 固定了,所以只要從 Q 開始掃描:
A 2 Q 9 K 5 3 8 6 4 7 10 J
    ^從這裡以後往右去找
=>
A 2 3 Q 9 K 5 8 6 4 7 10 J
^^^^^從頭到這裡已經排好了,排好的部份越來越多了!

依此類推。

另一種 Insertion Sort 的想法也是大家直覺上容易想到的作法,先把亂掉的十三張梅花理好展開,從第二張牌開始去和第一張比較,把兩張牌按順序排好,再來考慮第三張牌,去和前面兩張牌比較,將其插入在對應的位置,再來考慮第四張牌,去和前面三張牌比較,插入在對應的位置。舉例如下:
假設一開始亂掉的十三張梅花牌,理好展開長這樣:
Q 9 K 5 3 A 8 2 6 4 7 10 J

一開始拿第二張牌 9 和第一張牌 Q 比較,把 9 插在 Q 前面:
Q 9 K 5 3 A 8 2 6 4 7 10 J
=>
9 Q K 5 3 A 8 2 6 4 7 10 J

然後看第三張牌 K,去和前面兩張牌 9 和 Q 比對,將 K 放在對應的位置,因為 K 比 Q 大,所以位置不動:
9 Q K 5 3 A 8 2 6 4 7 10 J
    ^拿它去和左邊兩張牌比對
=>
9 Q K 5 3 A 8 2 6 4 7 10 J
^^^^^從頭到這裡已經排好了

再來看第四張牌 5,去和前面排好的 9、Q、K 比對,插入到對應的位置:
9 Q K 5 3 A 8 2 6 4 7 10 J
      ^拿它去和邊三張牌比對
=>
5 9 Q K 3 A 8 2 6 4 7 10 J
^^^^^^^從頭到這裡已經排好了,排好的部份越來越多了!

依此類推。

我覺得兩種都算是 Insertion Sort,不過第二種作法是我們會在教科書裡看到的方法,原因很簡單,因為第一種作法我會去按照數字 A 2 3 4... 這樣的順序搜尋,也就是我們做了一個假設:數列排好後是逐一遞增且每個元素都存在。但是這樣的假設每次都成立嗎?如果今天要排的十三張梅花牌中,被裁判隨機抽了兩張呢?因此第二種作法會是比較好的作法,也就是常看到的 Insertion Sort 演算法。

寫成虛擬程式碼長這樣:
Insertion_sort(A)
for j = 2 to length[A]
    key = A[j]

    // 底下部份將 key 安插在左邊已經排好的牌中
    i = j-1
    while(i > 0 and A[i] > key)
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key


我用 length[A] 代表 A 數列的長度。A[1] 代表數列的第一個元素,而 A[i] 代表第 i 個元素。注意到虛擬碼裡面常常以 1 為數列的第一個元素索引值,而不是程式設計裡面的 0 為索引值。

原則上虛擬程式碼的邏輯就是我們上面看過的第二種想法。寫成 C++ 的範例長的像下面這樣,我用了 template,並且假設數列可以做 iterator 的加減法運算,因此 array、std::vector 都可以使用。
// insertion.cpp
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

template<typename Iterator>
void insertion_sort(Iterator begin, Iterator end) {
    for(size_t j = 1; j < (end-begin); ++j) {
        auto key = *(begin+j);
        size_t i = j - 1;
        while(*(begin+i) > key) {
            *(begin+i+1) = *(begin+i);
            if(--i == (size_t)-1) break;
        }   
        if(i == (size_t)-1) *begin = key;
        else *(begin+i+1) = key;
    }   
}

int main() {
    vector<int> v;
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(v));
    insertion_sort(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << '\n';
}

存成檔案 insertion.cpp,編譯產生出 insertion 執行檔:
$ g++ -std=c++11 insertion.cpp -o insertion

執行:
$ echo "6 4 3 5 1 2" | ./insertion

輸出:
1 2 3 4 5 6

程式碼中為了應付大量測試資料,用了 <algorithm> 裡面的 std::copy,<vector> 的 std::vector,<iterator> 的 std::istream_iterator、std::ostream_iterator,和 std::back_inserter。

另外原來虛擬碼中是以索引值為 1 開始,為了換成程式碼,改成 0 開始。

沒有留言:

張貼留言