シェルソートをC言語でやってみる

AOJ ALDS1 2-D Shell Sortをやったのでノート代わりに書く。

・挿入ソートの改良版

・間隔を決めて挿入ソートしてどんどん間隔を狭めて挿入ソートするやつ

・計算量は間隔をどうとるかによって変わってくる

コード

#include <stdio.h>

int cnt = 0;

//挿入ソート
void insertionsort(int a,int n,int g){
    int i,v,j;

    for(i=g;i<=n-1;i++){
        v=a[i];
        j=i-g;//比較するためにgの間隔分前に戻す

        while(j>=0 && a[j]>v){//前の奴の方がでかいなら交換
            a[j+g]=a[j];
            j=j-g;//jがマイナスに行っても大丈夫
            cnt++;
        }
        a[j+g]=v;
        
    }
    return 0;
}

//シェルソート
void shellsort(int a,int n){
    int i;
    int m = 0;
    int g[100];//間隔
    g[0]=1;

    for(m=1;3*g[m-1]+1<=n;m++) {//決めた間隔分回す
        g[m]=3*g[m-1]-1;//間隔g[i]=1,2,5...
    }
    printf("%d\n",m);

    for(i=m-1;i>=0;i--){//print用
        if(i==m-1) printf("%d",g[i]);
        else printf(" %d",g[i]);
    }
    printf("\n");

    for(i=m-1;i>=0;i--){//間隔を狭めて挿入ソート
        insertionsort(a,n,g[i]);
    }
}

int main(){
    int n,i;
    scanf("%d",&n);
    int a[n];

    for(i=0;i<n;i++) scanf("%d",&a[i]);

    shellsort(a,n);

    printf("%d\n",cnt);

    for(i=0;i<n;i++) printf("%d\n",a[i]);
}