シェルソート(改訂版)

 前回のシェルソート(もどき)を見直して、むしろソートの部分を書き直してちゃんとしたシェルソートに直しました。
前回のはシェルソートでは無かったです。残念?

#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;
	}

	for (; n>0; n--) {
		h = (pow(3, n) -1) / 2;
		cout << "h= " << h << endl;
		//間隔で比較
		for (i=h; i<array_size; i++) {
			j = i;
			//ここで挿入ソート
			while (j >= h && a[j-h] > a[j]) {
				tmp = a[j];
				a[j] = a[j-h];
				a[j-h] = tmp;
				Display_array(a, count);
				j -= h;
			}
		}
	}

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

  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,
交換回数 7
13, 28, 34, 37, 53, 64, 75, 95,

前回より1回程交換回数が減ってますね。


 どこが間違ってたかといいますと、入れ替える部分で挿入ソートをしていなかったということです。なんという見落とし...。
 次回はいよいよクイックソートでも試してみようと思います。次のCの授業で構造体をやってくれるみたいなのでちょっと見直しておかないと。