整列アルゴリズムを比較する(改良挿入法(シェルソート)編)

どうも、켢켹켷君です。(？)
켢켹켷のUnicodeポイントをビット反転するとポテトになるってことです。
ちなみに朝の暇つぶしにPythonで作ったプログラムで変換しました。

ビット反転してしまった文字列

前回は挿入法をしました。

ということで今回は改良挿入法(シェルソート)です。

シェルソートとは、改良挿入法というくらいなので基本挿入法を基にしています。(基本挿入法は前回作った挿入法です)
シェルソートは、挿入法は既に整列された部分が多ければ処理が速いということを利用して、複数グループに分けて挿入法を繰り返していくという整列アルゴリズムです。
3つのグループ→2つのグループ→1つのグループ
とまとめていってそれぞれのグループで挿入法を行います。
例えば{6,7,5,2,9,8}は
1. (6,2),(7,9),(5,8)というグループで考えてそれぞれを挿入法で整列します。
→{2,7,5,6,9,8}
2. (2,5,9),(7,6,8)というグループで同じように処理
→{2,6,5,7,9,8}
3. 1つのグループとして処理(普通の挿入法)
→{2,5,6,7,8,9}
計算量とかはよく知りませんがO(n^2)より小さいらしいです。

ということでC++プログラムにしていきます。
省略部分は交換法編に載ってます。

2022/3/15 追記:プログラムが間違っていたので訂正したものに変えています

void shell(int array[],int array_size){
    int sw;
    for(int c=3;c>0;c--){
        for(int i=2;i<array_size;i+=c){
            for(int p=0;p<c;p++){
                for(int j=i-(i-p)%c+c+p;j>=c+p;j-=c){
                   if(array[j-c]<array[j])break;
                   else{
                       sw=array[j];
                       array[j]=array[j-c];
                       array[j-c]=sw;
                   }
                }
            }
        }
    }
}

for文がめちゃくちゃ入り子になってますね、1つ目はグループ数の制御、2つ目と4つ目は挿入法、3つ目はグループ毎に挿入法を行うためです。

ということでシェルソート編はここまで!
次回はクイックソート編です。また次回!