ヒープソートのアルゴリズムを実装してみた

ソート(並び替え)にはいくつかやり方がありますが、
今回はヒープソートというのを実装してみました。

ヒープソートが実際にどういうものなのかは、
動画で観た方が分かりやすいので、youtubeのリンクを
貼っておきますのでそちらをご覧ください。
https://www.youtube.com/watch?v=X0ESspSiLIc

ヒープソートはツリー上に見たてて、ソートをしていく処理ですね。

これをコードで書くとこうなります。

package sort;

/**
 * ヒープソート
 */
public class HeapSort {
	
	public static void main(String[] args) {
		
		// 配列(並び替えの対象)
		int array[] = {7, 4, 9, 2, 3, 8, 6, 1, 5};
		
		arrayPrint(array);
		sort(array);
		arrayPrint(array);
		
	}
	
	/**
	 * ソート処理
	 * @param array
	 */
	static public void sort(int array[]) {
		
		int length = array.length;
		
		for (int i = length / 2; 0 <= i; i--) {
			heap(array, length, i);
		}
		
		for (int i = length - 1; 0 <= i; i--) {
			if (array[i] < array[0]) {
				swap(array, 0, i);
				
				heap(array, i, 0);
			}
		}
	}
	
	/**
	 * ヒープの確認
	 * @param array
	 * @param lastNum
	 * @param root
	 */
	static public void heap(int array[], int lastNum, int root) {
		
		// 親ノード
		int parent = root;
		// 子ノード
		int child1 = 2 * root + 1;
		int child2 = 2 * root + 2;
		
		// (親・子)ノードの値の確認
		if (child1 < lastNum && array[parent] < array[child1]) {
			parent = child1;
		}
		if (child2 < lastNum && array[parent] < array[child2]) {
			parent = child2;
		}
		
		if (parent != root) {
			//　親ノードと子ノードの値を入れ替え
			swap(array, root, parent);
			
			heap(array, lastNum, parent);
		}
	}
	/**
	 * 配列入れ替え用
	 * @param array 配列
	 * @param num1
	 * @param num2
	 */
	static public void swap(int array[], int num1, int num2) {
		
		int tmp = array[num1];
		array[num1] = array[num2];
		array[num2] = tmp;
		
		arrayPrint(array);
	}
	
	/**
	 * 配列出力用
	 * @param array
	 */
	static public void arrayPrint(int array[]) {
		int count = 0;
		for (int a : array) {
			System.out.print(a);
			count++;
			if (count != array.length) {
				System.out.print(", ");
			}
		}
		System.out.println();
	}
}

動かしてみると分かりますが、こういう風にソートされていきます。

7, 4, 9, 2, 3, 8, 6, 1, 5
7, 4, 9, 5, 3, 8, 6, 1, 2
7, 5, 9, 4, 3, 8, 6, 1, 2
9, 5, 7, 4, 3, 8, 6, 1, 2
9, 5, 8, 4, 3, 7, 6, 1, 2
2, 5, 8, 4, 3, 7, 6, 1, 9
8, 5, 2, 4, 3, 7, 6, 1, 9
8, 5, 7, 4, 3, 2, 6, 1, 9
1, 5, 7, 4, 3, 2, 6, 8, 9
7, 5, 1, 4, 3, 2, 6, 8, 9
7, 5, 6, 4, 3, 2, 1, 8, 9
1, 5, 6, 4, 3, 2, 7, 8, 9
6, 5, 1, 4, 3, 2, 7, 8, 9
6, 5, 2, 4, 3, 1, 7, 8, 9
1, 5, 2, 4, 3, 6, 7, 8, 9
5, 1, 2, 4, 3, 6, 7, 8, 9
5, 4, 2, 1, 3, 6, 7, 8, 9
3, 4, 2, 1, 5, 6, 7, 8, 9
4, 3, 2, 1, 5, 6, 7, 8, 9
1, 3, 2, 4, 5, 6, 7, 8, 9
3, 1, 2, 4, 5, 6, 7, 8, 9
2, 1, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 3, 4, 5, 6, 7, 8, 9

あえて途中経過を出力させて、変化の様を追ってみました。
アルゴリズムの勉強で一度書いてみて、デバッグで追ってみるのも良いかもです。

ヒープソートのコード紹介でした。