シェルソート

 C++で書いてみました。
シェルソートは安定ソートではない。
http://www.geocities.jp/ky_webid/algorithm/index.html ここら辺を参考にして下さい。


 ソースの前にちょっと解説。


 wikipedia ここを見たところ、間隔hはh_{n+1}=3h_n + 1としてあげるといいようなのでこれを解いてh=\frac{1}{2}(3^n -1)としてます。

#include <iostream>
#include <math.h> //累乗使うため
#define array_size 8 
// 配列の大きさ。とりあえず8つで。

using namespace std;

void Display_array(int *, int &); 
// 配列の中身を表示する関数。(勝手に作成)

int main()
{
	int count = 0;	//Display_arrayの回数計算用(つまり値交換回数)
	int a[array_size] = {28,95,37,53,64,13,75,34};
	Display_array(a, count);
	
	int i, j, n, h=1, tmp; // hの初項1
	
	/*	交換処理の間隔を計算	*/
	for (n=1; ; n++) {
		h = 3 * h + 1;
		if (h > array_size) break;
	}

	std::cout << "シェルソート開始" << endl;
	
	for (i=n; i>0; i--) {	//シェルソート
		h = (pow(3, i) - 1) / 2;	
//第n項目の間隔
		std::cout << "hの値, " << h << endl;
		for (j=0; j<array_size - h; j++) {
			if (a[j] > a[j+h]) {
				tmp = a[j];
				a[j] = a[j+h];
				a[j+h] = tmp;
				Display_array(a, count);
			}
		}
			std::cout << endl; //見やすくするため改行
	}

	std::cout << "挿入ソート開始" << endl;
	
	for (i=1; i<array_size; i++) {	//挿入ソート
		for (j=i; j>=1; j--) {
			if (a[j] < a[j-1]) {
				tmp = a[j];
				a[j] = a[j-1];
				a[j-1] = tmp;
				Display_array(a, count);
			}
		}
		std::cout << endl; //見やすくするため改行
	}


	Display_array(a, count);
	std::cout << "交換回数 " << count-2 << endl;	
//最初と最後の表示はカウントしないため。

  return 0;
}

void Display_array(int *a, int &count)
{
	int i;
	for (i=0; i<array_size; i++) {	//配列を表示する
		std::cout << a[i] << ", ";
	}
	std::cout << endl;	//見やすく改行
	
	count++;	//カウントを1増やす
}

これはシェルソートした後に挿入ソートしてます。
実行結果

28, 95, 37, 53, 64, 13, 75, 34,
シェルソート開始
hの値, 4
28, 13, 37, 53, 64, 95, 75, 34,
28, 13, 37, 34, 64, 95, 75, 53,

hの値, 1
13, 28, 37, 34, 64, 95, 75, 53,
13, 28, 34, 37, 64, 95, 75, 53,
13, 28, 34, 37, 64, 75, 95, 53,
13, 28, 34, 37, 64, 75, 53, 95,

挿入ソート開始





13, 28, 34, 37, 64, 53, 75, 95,
13, 28, 34, 37, 53, 64, 75, 95,


13, 28, 34, 37, 53, 64, 75, 95,
交換回数8

(交換が発生したところでDisplay_arrayという関数を読んでいます。どこが変化してるのかがわかりやすいようにするのと、交換した回数を数えるため。)
ちなみに上のソースでシェルソートのforの部分をコメントアウトすると挿入ソートのみになります。
挿入ソートだけの場合の実行結果

28, 95, 37, 53, 64, 13, 75, 34,
挿入ソート開始

28, 37, 95, 53, 64, 13, 75, 34,

28, 37, 53, 95, 64, 13, 75, 34,

28, 37, 53, 64, 95, 13, 75, 34,

28, 37, 53, 64, 13, 95, 75, 34,
28, 37, 53, 13, 64, 95, 75, 34,
28, 37, 13, 53, 64, 95, 75, 34,
28, 13, 37, 53, 64, 95, 75, 34,
13, 28, 37, 53, 64, 95, 75, 34,

13, 28, 37, 53, 64, 75, 95, 34,

13, 28, 37, 53, 64, 75, 34, 95,
13, 28, 37, 53, 64, 34, 75, 95,
13, 28, 37, 53, 34, 64, 75, 95,
13, 28, 37, 34, 53, 64, 75, 95,
13, 28, 34, 37, 53, 64, 75, 95,

13, 28, 34, 37, 53, 64, 75, 95,
交換回数 14

 どうでしょうか?シェルソートの部分を余計にforで回っているのにもかかわらず、挿入ソートのときよりも交換回数が6回も少ないのです。
 シェルソートで大まかに並べ替えてから、挿入ソートをしてあげることで高速に並べ替えることが出きるのです。
 ということでこれがシェルソートです。学校でやったバブルソートなんて目じゃないぜ!(意味不明)


追記:自分なりに書いた物なのでおそらく無駄が多い気がします。むしろほかのサイトのプログラムとかなり違うので今更ながら「あれ?」なんて思ってますが気にしない...。
 次回あたりにクイックソートを見てみようと思います。
ソートではないですが、正規表現をいじってみたかったりします。