アルゴリズムとデータ構造 (1)

挿入ソート

挿入ソートのアルゴリズム

配列 a にソートする要素が入っているとする．
ただし，a[0] は特別の目的で使うので，a[1] 以後に対象とする要素があるものとする．
a[1] から a[i-1] まですでにソートされているとき，a[i] をこの中の適当な位置に挿入してソートする方法である．
a[i] 要素の挿入で a[1] から a[i] がソートされたことがわかる．
a[0] に a[i] と同じ要素を入れているが，これを番兵 (Pivot) と呼ぶ．番兵を使うことで，配列のインデックスのチェックをする必要がなくなる．

挿入法ソートのアルゴリズム

    void sort() {					// 挿入ソート(昇順)
	int work, j;
	for (int i = 2; i <= length; i++) {
	    work = a[i];				// a[i]に注目する
	    a[0] = work;				// 番兵の設定
	    j = i - 1;					// a[i-1] を比較対象にする
	    while (work < a[j]) {			// work より値が大きい間続ける
		a[j + 1] = a[j];			// work より大きい物を一つ後ろに移動
		j = j - 1;				// a[j-1] を次の比較対象にする
	    }
	    a[j + 1] = work;				// workの値を挿入
	}
    }

挿入ソートをアニメーションにしてみると

一番左に少しはなれてあるのが a[0] の要素(番兵)である．
ソート実行中は黄色になり，比較する要素が緑色，移動は青色のところから赤色のところへ行われる．
ソートが終了するとピンク色になる．

挿入ソートのプログラム

プログラム

// InsertionSortMain.java

class InsertionSortMain {

    static int a [];				// ソートする対象を置く配列
    static int length = 11;			// 配列の長さ (初期値)
    static InsertionSort iSort;			// ソートオブジェクト変数

    public static void main (String args[]) {	// ここから実行が始まる
	if (args.length != 0) {			// コマンドの引数を配列の長さに設定
	    length = new Integer(args[0]).intValue() + 1;
	}
	a = new int[length];			// 配列を作成
	iSort = new InsertionSort();		// 挿入ソートオブジェクトの生成
	initialize();				// 配列の初期値設定
	print("befor");				// ソートする対象の表示
	iSort.sort();				// ソートの実行
	print("after");				// ソート結果の表示
    }

    static void initialize() {			// 配列の初期値設定メソッド
	for (int i = 1; i < length; i++) {	// 乱数を使って配列の値設定を行う
	    a[i] = (int) (length * 100 * Math.random());
	}
	iSort.set(a);				// ソートオブジェクトに配列値を設定
    }

    static void print(String string) {		// 配列要素値の表示メソッド
	a = iSort.get();			// ソートオブジェクトから配列値を獲得
	System.out.println(string + ":  ");	// 値の表示
	for (int i = 1; i < length; i++) {
	    System.out.println("" + a[i] + "  ");
	}
	System.out.println();
    }

}

/* 挿入ソート */
class InsertionSort {

    int a [];					// ソートする要素をおく配列

    void sort() {				// 挿入ソート(昇順)
	int work, j;
	for (int i = 2; i < a.length; i++) {
	    work = a[i];			// a[i]に注目
	    a[0] = work;			// 番兵の設定
	    j = i - 1;				// a[i-1]を比較対象にする
	    while (work < a[j]) {		// workより値が大きい間続ける
		a[j + 1] = a[j];		// workより値が大きい物を一つ後ろに移動
		j = j - 1;			// a[j-1]を次の比較対象にする
	    }
	    a[j + 1] = work;			// workの値を挿入
	}
    }

    void swap(int i, int j) {			// 要素の交換
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
    }

    void set (int [] a) {			// 配列への値設定
	this.a = a;
    }

    int [] get() {				// 配列を返す
	return(a);
    }

}

挿入ソートの計算量

挿入法ソートの計算量も平均では O(n²) であるが，データによってはもっと早くソートが行われることもあり，選択ソートに較べて優れている．
内側のループを回る回数は，i に対して平均して (i-1)/2回であるから，全体では，
になる．
最悪の場合の繰り返し回数は，
である．
比較の回数は平均も最悪の場合もこれより n-1 回多い．

演習6.3

挿入ソートの要素比較回数，要素交換回数を数えるプログラムを作りなさい．

次の資料へトップページへ