ソート（ Java ）

バブルソート

　　以下においては，100,000 個（ヒープソートとクイックソートの場合は 5,000,000 個）のデータを乱数によって生成し，それを昇順及び降順にソートし，データの生成時間（ data の後ろ）及びソートに要した時間（ sort の後ろ）を出力しています．なお，昇順及び降順は，関数名を引数として渡すことによって制御しています（ 72 行目，82 行目と対応する関数）．勿論，前章で述べた比較演算子の多重定義を使用しても可能です．バブルソートの手順は以下に示すとおりです．

配列 data に n 個のデータが入っているものとする．　i = 0, 1, ･･･, n-1
i 番目のデータと i+1 番目のデータを比較し，もし，

data[i+1] < data[i]　（昇順の場合）

であればそれらのデータを交換する．　i = 0, 1, ･･･, n-2

→ この結果，data[n-1] に最も大きなデータが入ることになる
次に，n-1 個のデータに対し上の処理を繰り返す．
同様に，n-2，n-3，・・・個のデータに対して同じ処理を繰り返す

/****************************/
/* バブルソート             */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N      = 100000;
		int data[] = new int [N];
		Random rn  = new Random();
			// 昇順
		long tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		long tm2 = System.currentTimeMillis();
		bubble(N, data, 0);
		long tm3 = System.currentTimeMillis();
		System.out.printf("昇順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
			// 降順
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		tm2 = System.currentTimeMillis();
		bubble(N, data, 1);
		tm3 = System.currentTimeMillis();
		System.out.printf("降順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
	}

	/***********************************/
	/* ２つのデータを交換する          */
	/*      data : データ              */
	/*      i,j : ２つのデータの添え字 */
	/***********************************/
	static void swap(int data[], int i, int j)
	{
		int temp = data[i];
		data[i]  = data[j];
		data[j]  = temp;
	}

	/***********************/
	/* バブルソート        */
	/*      n : データの数 */
	/*      data : データ  */
	/*      cp : =0 : 昇順 */
	/*           =1 : 降順 */
	/***********************/
	static void bubble(int n, int data[], int cp)
	{
		int sw = 0;
		for (int i1 = n; i1 > 1; i1--) {
			for (int i2 = 0; i2 < i1-1; i2++) {
				if (cp == 0 && data[i2] > data[i2+1] || cp > 0 && data[i2] < data[i2+1]) {
					sw = 1;
					swap(data, i2, i2+1);
				}
			}
			if (sw == 0)
				break;
		}
	}
}

（出力）

昇順（データ数： 100000）
   data 4 ms
   sort 23900 ms
降順（データ数： 100000）
   data 2 ms
   sort 24941 ms

選択ソート

　　ここでも，バブルソートと同様の処理を行っています．また，選択ソートの手順は以下に示すとおりです．

配列を走査して，最も小さな要素を見つけだす（昇順の場合）．
見つけたら，それを配列の先頭要素と交換する．
上記の操作を配列の 2 番目の要素から始まるサブ配列について繰り返す．

/****************************/
/* 選択ソート               */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N      = 100000;
		int data[] = new int [N];
		Random rn  = new Random();
			// 昇順
		long tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		long tm2 = System.currentTimeMillis();
		select(N, data, 0);
		long tm3 = System.currentTimeMillis();
		System.out.printf("昇順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
			// 降順
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		tm2 = System.currentTimeMillis();
		select(N, data, 1);
		tm3 = System.currentTimeMillis();
		System.out.printf("降順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
	}

	/***********************************/
	/* ２つのデータを交換する          */
	/*      data : データ              */
	/*      i,j : ２つのデータの添え字 */
	/***********************************/
	static void swap(int data[], int i, int j)
	{
		int temp = data[i];
		data[i]  = data[j];
		data[j]  = temp;
	}

	/***********************/
	/* 選択ソート          */
	/*      n : データの数 */
	/*      data : データ  */
	/*      cp : =0 : 昇順 */
	/*           =1 : 降順 */
	/***********************/
	static void select(int n, int data[], int cp)
	{
		int k = 0;
		for (int i1 = n; i1 > 1; i1--) {

			int m = k;
			for (int i2 = k+1; i2 < n; i2++) {
				if (cp == 0 && data[m] > data[i2] || cp > 0 && data[m] < data[i2])
					m = i2;
			}

			if (m != k)
				swap(data, k, m);

			k++;
		}
	}
}

（出力）

昇順（データ数： 100000）
   data 4 ms
   sort 11876 ms
降順（データ数： 100000）
   data 2 ms
   sort 12058 ms

バケツソート

　　バケツソートとは，一次元配列に入っている n 個の正の整数をバケツ配列と呼ばれる 10 × (n-1) の二次元配列を使用してソートする方法であり，以下に示すような手続きに従がいます．

一次元配列の各数値を一の位に基づいてバケツ配列の対応する各行に格納する．たとえば，一次元配列の中に数値 97，3，100 がこの順序で入っていたとすると，97 は行 7，3 は行 3，100 は行 0 に格納される．これを「分配パス」と呼ぶ．
バケツ配列の各行に格納されている値を行 0 から順番に元の一次元配列の戻す．これを「収集パス」という．この時点で，一次元配列の中の値は 100，3，97 の順序になる．
以上の処理を数値の各位について繰り返す．

/****************************/
/* バケツソート             */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N      = 5000000;
		int data[] = new int [N];
		int num[]  = new int [10];
		int bu[][]  = new int [10][];
		for (int i1 = 0; i1 < 10; i1++)
			bu[i1] = new int [N];
		Random rn  = new Random();
			// 昇順
		long tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = Math.abs(rn.nextInt());
		long tm2 = System.currentTimeMillis();
		bucket(N, data, 0, 1, bu, num);
		long tm3 = System.currentTimeMillis();
		System.out.printf("昇順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
			// 降順
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = Math.abs(rn.nextInt());
		tm2 = System.currentTimeMillis();
		bucket(N, data, 1, 1, bu, num);
		tm3 = System.currentTimeMillis();
		System.out.printf("降順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
	}

	/********************************************/
	/* バケツソート                             */
	/*      n : データの数                      */
	/*      data : データ                       */
	/*      cp : 比較方法（=0 : 昇順，=1 : 降順 */
	/*      k : 桁                              */
	/*      bu : バケツ                         */
	/*      num : 各バケツに入っているデータ数  */
	/********************************************/
	static void bucket(int n, int data[], int cp, int k, int bu[][], int num[])
	{
		int kk = 1, sw1 = 1, sw2 = 0;
			// 準備
		for (int i1 = 0; i1 < k-1; i1++)
			kk *= 10;
		for (int i1 = 0; i1 < 10; i1++)
			num[i1] = 0;
			// 分配パス
		for (int i1 = 0; i1 < n; i1++) {
			if (data[i1] >= 10*kk)
				sw2 = 1;
			int k1 = (data[i1] / kk) % 10;
			if (num[k1] >= n-1)
				sw1 = 0;
			else {
				bu[k1][num[k1]] = data[i1];
				num[k1]++;
			}
		}
			// 収集パス
		if (sw1 > 0) {
			int k1 = 0;
			if (cp == 0) {
				for (int i1 = 0; i1 < 10; i1++) {
					for (int i2 = 0; i2 < num[i1]; i2++) {
						data[k1] = bu[i1][i2];
						k1++;
					}
				}
			}
			else {
				for (int i1 = 9; i1 >= 0; i1--) {
					for (int i2 = 0; i2 < num[i1]; i2++) {
						data[k1] = bu[i1][i2];
						k1++;
					}
				}
			}
		}
			// 次の桁
		if (k < 10 && sw2 > 0)
			bucket(n, data, cp, k+1, bu, num);
	}
}

（出力）

昇順（データ数： 5000000）
   data 93 ms
   sort 639 ms
降順（データ数： 5000000）
   data 91 ms
   sort 608 ms

ヒープソート

　　ヒープという言葉によって，プログラム実行時に任意に確保や解放を繰り返すことができるメモリ領域（ヒープ領域，ヒープメモリ，heap memory ）を指す場合があります．しかし，ここで使用するヒープとは，木構造の一種であり，親ノードの値が子ノードの値より常に大きい（または，小さい）という条件を満たしています．一般的には，各ノードが最大で 2 つの子ノードしか持たないバイナリヒープを意味します．ヒープソートは，次に述べるクイックソートよりも多少遅いですが，非常に高速なソートであり，その手順は以下に示すとおりです．

整列対象の配列内にボトムアップでヒープを構築する．
構築されたヒープの先頭要素 [0] と最後の要素 [N-1] を交換する．
先頭要素 [0] から最後の一つ前の要素 [N-2] でヒープを再構成する．
最後の要素を [N-2] として（ N = N - 1 ），手順 B に戻る．
N が 0 となった時点で終了する．

　　上の説明だけでは分かり難いと思いますので，ソート対象のデータ，

int data[] = {1, 4, 2, 9, 0, 2, 8, 7, 3, 5}

を昇順に並べたい場合を例にとって説明します．昇順に並べるためには，ルートノードが最も大きいヒープ（親ノードの値が子ノードの値より常に大きいヒープ）を生成する必要があります．実際，上に示したデータ全体に対してヒープを生成すると以下のようになります．

{9, 7, 8, 4, 5, 2, 2, 1, 3, 0}
	親 [0] 子 [1], [2]
	親 [1] 子 [3], [4]
	親 [2] 子 [5], [6]
	親 [3] 子 [7], [8]
	親 [4] 子 [9]

　　一般に，

data[k] : 親
	data[k1], data[k2] : 子供，k1 = 2k+1, k2 = 2k+2
	子供から見て親は：(k1-1) / 2 = (k2-1) / 2 = k

のような形でヒープが生成されます．

/****************************/
/* ヒープソート             */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N      = 5000000;
		int data[] = new int [N];
		Random rn  = new Random();
			// 昇順
		long tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = Math.abs(rn.nextInt());
		long tm2 = System.currentTimeMillis();
		heap(N, data, 0);
		long tm3 = System.currentTimeMillis();
		System.out.printf("昇順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
			// 降順
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = Math.abs(rn.nextInt());
		tm2 = System.currentTimeMillis();
		heap(N, data, 1);
		tm3 = System.currentTimeMillis();
		System.out.printf("降順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
	}

	/***********************************/
	/* ２つのデータを交換する          */
	/*      data : データ              */
	/*      i,j : ２つのデータの添え字 */
	/***********************************/
	static void swap(int data[], int i, int j)
	{
		int temp = data[i];
		data[i]  = data[j];
		data[j]  = temp;
	}

	/**********************************/
	/* ヒープの生成                   */
	/*      n : データの数            */
	/*      data : データ             */
	/*      parent : 親のインデックス */
	/*      cp : =0 : 昇順            */
	/*           =1 : 降順            */
	/**********************************/
	static void heap_c(int n, int data[], int parent, int cp)
	{
			// 子ノードのインデックス
		int child = (2 * parent) + 1;
			// 親ノードの値
		int temp = data[parent];
			// ヒープの生成
		while (child < n) {
					// 値が大きい（小さい）ほうの子ノードを選択する。
			if (child < n-1 && (cp == 0 && data[child + 1] > data[child] || cp > 0 && data[child + 1] < data[child]))
				child = child + 1;
					// 親ノードの値が子ノードの値より大きい（小さい）場合は何もしない。
			if (cp == 0 && temp > data[child] || cp > 0 && temp < data[child])
				break;
			else {   // temp が data[child] 以下（以上）の場合
					// 親の要素に子を入れる
				data[(child - 1) / 2] = data[child];
					// 子ノードのインデックスを進める。
				child = (2 * child) + 1;
			}
		}
			// 親ノードとなる要素（最後の子供）に値を入れる
		data[(child - 1) / 2] = temp;
	}

	/***********************/
	/* ヒープソート        */
	/*      n : データの数 */
	/*      data : データ  */
	/*      cp : =0 : 昇順 */
	/*           =1 : 降順 */
	/***********************/
	static void heap(int n, int data[], int cp)
	{
			// ヒープの生成
			//    data[k] : 親
			//    data[k1], data[k2] : 子供，k1 = 2k+1, k2 = 2k+2
			//       子供から見て親は：(k1-1) / 2 = (k2-1) / 2 = k
			// 例 {1, 4, 2, 9, 0, 2, 8, 7, 3, 5}
			// 結果 {9, 7, 8, 4, 5, 2, 2, 1, 3, 0}   昇順の場合
			//    親 [0] 子 [1], [2]
			//    親 [1] 子 [3], [4]
			//    親 [2] 子 [5], [6]
			//    親 [3] 子 [7], [8]
			//    親 [4] 子 [9]
		for (int i1 = (n-1) / 2; i1 >= 0; i1--)
			heap_c(n, data, i1, cp);
			// ヒープソート実行
		for (int i1 = n - 1; i1 > 0; i1--) {
			swap(data, 0, i1);   // 先頭を最後と交換
			heap_c(i1, data, 0, cp);   // 残りの部分に対するヒープの生成
		}
	}
}

（出力）

昇順（データ数： 5000000）
   data 94 ms
   sort 1877 ms
降順（データ数： 5000000）
   data 94 ms
   sort 1901 ms

クイックソート

　　クイックソートの手順は以下に示すとおりです．例えば，次のようなデータが与えられたとしまする．このとき，左端のデータ（ 37 ）を枢軸要素と呼び，この要素がソート後の正しい位置にくるように以下の処理を行います（昇順の場合）．

37 2 6 4 89 8 10 12 68 45

配列の右端の要素から順に枢軸要素 ( 37 ) と比較していき 37 より小さな要素があれば，その要素を 37 と交換する．

12 2 6 4 89 8 10 37 68 45
配列の左端（正確には，上で 37 と交換した 12 の直後の要素）から順に枢軸要素 ( 37 ) と比較していき，37 より大きな要素があれば，その要素を 37 と交換する．

12 2 6 4 37 8 10 89 68 45
配列の右端（正確には，上で 37 と交換した 89 の直前の要素）から順に枢軸要素 ( 37 ) と比較していき，37 より小さな要素があれば，その要素を 37 と交換する．

12 2 6 4 10 8 37 89 68 45
以上の結果，37 の左には 37 より大きな要素はなく，またその右側には 37 より小さな要素は無い状態となる．つまり，37 は，ソート後の正しい位置にあることがわかる．
37 の左側の配列（ 12 2 6 4 10 8 ），及び，右側の配列（ 89 68 45 ）に対して以上の処理を再帰的に繰り返す．

　　このプログラムでは，Arrays クラスの sort を利用した場合についても検討しています．

/****************************/
/* クイックソート           */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N      = 5000000;
		int data[] = new int [N];
		Random rn  = new Random();
			// 昇順
		long tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		long tm2 = System.currentTimeMillis();
		quick(0, N, data, 0);
		long tm3 = System.currentTimeMillis();
		System.out.printf("昇順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);

		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		tm2 = System.currentTimeMillis();
		Arrays.sort(data);
		tm3 = System.currentTimeMillis();
		System.out.printf("      ***Arrays.sort の利用***\n");
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
			// 降順
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data[i1] = rn.nextInt();
		tm2 = System.currentTimeMillis();
		quick(0, N, data, 1);
		tm3 = System.currentTimeMillis();
		System.out.printf("降順（データ数： %d）\n", N);
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);

		Integer data1[] = new Integer [N];
		tm1 = System.currentTimeMillis();
		for (int i1 = 0; i1 < N; i1++)
			data1[i1] = new Integer(rn.nextInt());
		tm2 = System.currentTimeMillis();
		Comparator<Integer> cp = new Comp();
		Arrays.sort(data1, cp);
		tm3 = System.currentTimeMillis();
		System.out.printf("      ***Arrays.sort の利用***\n");
		System.out.printf("   data %d ms\n", tm2-tm1);
		System.out.printf("   sort %d ms\n", tm3-tm2);
	}

	/***********************************/
	/* ２つのデータを交換する          */
	/*      data : データ              */
	/*      i,j : ２つのデータの添え字 */
	/***********************************/
	static void swap(int data[], int i, int j)
	{
		int temp = data[i];
		data[i]  = data[j];
		data[j]  = temp;
	}

	/*****************************/
	/* クイックソート            */
	/*      p : 先頭インデックス */
	/*      n : データの数       */
	/*      data : データ        */
	/*      cp : =0 : 昇順       */
	/*           =1 : 降順       */
	/*****************************/
	static void quick(int p, int n, int data[], int cp)
	{
		int left = p+1, right = p+n-1, pos = p, sw1 = 1, sw2;
			// 枢軸要素を正しい位置に置く
		while (sw1 > 0) {

			sw1 = 0;

			if (right-pos > 0) {
				sw2 = 0;
				for (int i1 = right; i1 > pos && sw2 == 0; i1--) {
					if (cp == 0 && data[pos] > data[i1] || cp > 0 && data[pos] < data[i1]) {
						swap(data, pos, i1);
						sw1   = 1;
						sw2   = 1;
						pos   = i1;
						right = i1 - 1;
					}
				}
			}

			if (pos-left > 0) {
				sw2 = 0;
				for (int i1 = left; i1 < pos && sw2 == 0; i1++) {
					if (cp == 0 && data[i1] > data[pos] || cp > 0 && data[i1] < data[pos]) {
						swap(data, pos, i1);
						sw1  = 1;
						sw2  = 1;
						pos  = i1;
						left = i1 + 1;
					}
				}
			}

			if (right-pos <= 0)
				sw1 = 0;
		}
			// サブ配列の処理
		if (pos > p+1)
			quick(p, pos-p, data, cp);
		if (pos < p+n-2)
			quick(pos+1, p+n-1-pos, data, cp);
	}
}

class Comp implements Comparator <Integer> {
	public int compare (Integer arg1, Integer arg2)
	{
		return arg2.compareTo(arg1);
	}
}

（出力）

昇順（データ数： 5000000）
   data 87 ms
   sort 956 ms
      ***Arrays.sort の利用***
   data 84 ms
   sort 480 ms
降順（データ数： 5000000）
   data 86 ms
   sort 1057 ms
      ***Arrays.sort の利用***
   data 750 ms
   sort 3106 ms

ソート（並べ替え，Java）