舉例,假設一開始亂掉的十三張梅花牌,理好展開長這樣:
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 開始。
沒有留言:
張貼留言