挿入ソート

insertion-sort.png

トランプ遊びで手札をソートするときに多くの人が使う手法である。
トランプの場合は

  1. まず左手を空にする
  2. テーブルの上にカードを裏向きに置く
  3. テーブルから1枚ずつカードを取って、左手の正しい位置に挿入していく

カードの正しい位置は、右から左へと順にすでに手の中にあるカードと比較すれば発見できる。

どの時点でも、左手にあるカードはソート済みである。
STLで既にソート関数はあるけど、ここはお勉強のため、実装してみよう。

#include <iostream>
using namespace std;
 
void main(){
    int array[]={5,2,4,6,1,3};
    cout<<"before:"<<endl;
    for(int i=0;i<sizeof(array)/sizeof(array[0]);i++){cout<<array[i]<<",";}
    cout<<endl;
    //挿入ソート jは左手に挿入しようとしている「現在のカード」を示す。
    for(int j=1;j<sizeof(array)/sizeof(array[0]);j++){
    //0~j-1番目までが「現在左手にあるカード」で「ソート済み」である。
        int key=array[j];
            //a[j]をソート済みの配列に挿入する
        int i=j-1;
        while(i>=0 && array[i]>key){
        //keyより大きいものが左側にあったら、それは順番違反なので並び替える
            array[i+1]=array[i];
            i=i-1;
        }
        array[i+1]=key;
    }
 
    cout<<"after:"<<endl;
    for(int i=0;i<sizeof(array)/sizeof(array[0]);i++){cout<<array[i]<<",";}
}

出力結果
before:
5,2,4,6,1,3,
after:
1,2,3,4,5,6,

なにが起こっているのか?step by stepで説明しよう。
まず、初期状態はこうなっている。

i=j-1;

の部分を図示すると。


keyはj番目の値で初期化してある。
keyとi番目の中身を比べてi番目の中身の方が多かったらiとjの内容を取り替えっこする。
iは取り替えっこ作業するたびに左に移動する。
iが配列の範囲を超えてしまったら
あるいは
i番目の中身とkeyの中身を比べて、i番目の中身の方少なかったら
ループ終了。

array[i+1]=array[i];

のときに、array[i+1]の中身が永遠に消えちゃう!と心配になるが、
この作業が終わったら、i+1番目の要素にkeyを入れるから大丈夫。
i+1番目に入れるってことは、iが抜けた直前の要素に入れるってこと。
つまり、最後に入れ替えっこして消えたやつだ。

サポートサイト Wikidot.com