C言語でシェルソート
シェルソートとは
・シェルさんが発表したソートアルゴリズムでクイックソートが発見されるまでは最高速のソートアルゴリズムとして知られていたらしい。
・単純なソートアルゴリズムと知られる挿入ソートにひと手間加えて計算量を挿入ソートでは"O(n^2)"だったのを"O(n^(1.25))~O(n^1.5)"まで減らした。
※挿入ソートとは
・バブルソートなどと同じ単純なソートアルゴリズムに数えられる。
イメージは箱の中身をすべて一回出して一つずつ箱に入れていく。その時にすでに入っている箱の中身と比較してしかるべき場所に挿入する。これをn-1回(最初の一つはすでに箱の中に入れているため)繰り返して要素を整列させていく。
最大でn*(n-1)/2回の比較がされるが、すでに整列されているものをソートにかけると(n-1)回で済む。つまり、ソート前の要素が整列されていればその分比較回数が減る。
追記: 交換回数は平均n/2回(多分)
挿入ソートと何が違うのか
・変数hを用いて要素をhの間隔で挿入ソートを行い、その間隔を狭めていき最終的にh=1で挿入ソートを行う。
大まかに挿入ソートを行っていき少しずつ細かくしていくイメージ。ただし、間隔hが常に偶数または奇数の場合比較されるものが変わらないためシェルソートの強みは発揮できない。
何回も挿入ソートを行うのでぱっと見計算量がもとより増えると思うかもしれないが、ある程度ソートされたものをソートしていくのでそれぞれのソートの効率がよく、計算量が減る。
※シェルソートの数学的な解析は完全にはされていないらしい
コード
#include <stdio.h> #include <stdlib.h> void shell_sort(int*, int); //シェルソートのプロトタイプ宣言 //void insertion_sort(int*, int); //挿入ソートのプロトタイプ宣言 void swap(int*, int*); //要素入れ替えのプロトタイプ宣言 int main(void) { int n; //データ数 scanf("%d", &n); //データ数入力 int a[n]; //ソート対象の配列 srand(0); //初期化 for (int i = 0; i < n; i++) { a[i] = rand(); //ランダムに配列の要素を決定 } for (int i = 0; i < n; i++) { //ソート前の配列要素の表示 if(i == 0) printf("%d", a[i]); else printf(" %d", a[i]); } printf("\n"); shell_sort(a, n); //シェルソート for (int i = 0; i < n; i++) { //ソート後の配列要素の表示 if(i == 0) printf("%d", a[i]); else printf(" %d", a[i]); } printf("\n"); return 0; } //シェルソート void shell_sort(int a[], int n) { int h, i, j; for (h = 1; h < n/9; h = h*3+1); //間隔hの決定 for (; h > 0; h /= 3) { //間隔hを狭めていく for (i = h; i < n; i++) { //ここから挿入ソート j = i; while ((j >= h) && (a[j-h] > a[j])) { swap(&a[j], &a[j-h]); j -= h; } } } return; } //挿入ソート /* void insertion_sort(int a[], int n) { int i, j; for (i = 1; i < n; i++) { j = i; while ((j >= 1) && (a[j-1] > a[j])) { swap(&a[j], &j[j-1]); j--; } } return; } */ //入れ替え void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; return; }
実行結果
20 38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680 38 281 1142 2437 2997 5853 7719 8365 8855 8945 10450 11797 14680 15921 20537 21238 26285 28100 30612 32285
