挿入ソート

http://www.geocities.jp/ky_webid/algorithm/004.html

挿入ソートの実装です。

1番目と2番目を比較し、順番が逆であれば入れ換える。次に、3番目の要素を、正しい順に並ぶように「挿入」する。（挿入する際、右側のデータを後ろに一つずつずらす）この操作で、3番目までのデータが整列済みとなる（但し、データが挿入される可能性があるので確定ではない）。このあと、4番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

挿入ソート - Wikipedia

む、難しい。

とりあえずコードの綺麗さは度外視でまずこの仕様を実現できるように実装してみます。

#include <stdio.h>

#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

void swap (int *a, int *b) {
    int work = *a;
    *a = *b;
    *b = work;
}

void insert_sort (int *data,int array_size) {
    int i,j,k;
    
    if ( array_size <= 1 ) {
        return;
    }
    
    for(i=1;i<array_size;++i) {
        for(j=0;j<i;++j){
            if ( data[i] < data[j] ) {
                for(k=i;k>j;k--){
                    swap(&data[k],&data[k-1]);
                }
            }
        }
    }
}

int main (void) {
    int num[] = { 3,9,11,50,6,34,20,98,6,1 };
    int i;
    
    insert_sort(num,ARRAY_NUM(num));
    
    for(i=0;i<ARRAY_NUM(num);i++){
        printf("%d ",num[i]);
    }
}

できました。

頭の中で考えていた分には凄い難しそうなイメージがあったんですが、いざ実装し始めてみたらそれ程でもありませんでした。

また交換処理が毎回出てくるのでswapという関数を作りました。今後はこのswapを使います。

ひとつだけ気になった部分があるのですが、配列を一つずつずらす処理が他になにか良い方法あるのかどうか。

今のやり方は単純で、対象のデータを左に一つずつ交換しながら移動させてるだけなのです。ちょうどバブルソートのような感じですね。

これって実はどーんとデータをずらせる方法があったりするのでしょうか。

解答例との比較

    for(i=1; i<ARRAY_SIZE; ++i)  /* ソートされていない部分の先頭要素の添字 */
    {
        for(j=i; j>=1 && array[j] < array[j-1]; --j) /* ソート済み部分を後ろから進む */
        {
            work = array[j];
            array[j] = array[j-1];
            array[j-1] = work;
        }
    }

美しいですねー。やってることは基本的には僕のコードと殆ど同じです。

ただこれが美しいのは内側のループを末尾からの走査にしてるところですね。

こうすることで値の検証と、一つずらす作業を同時に行っています。凄いです。

僕の場合は、先頭から走査していき、対象のデータを見つけたら今度は逆に左に戻っていくという実装になってるので二度手間なんですよね。

この発想はなかったです。悔しいです！