ソート(並び替え)にはいくつかやり方がありますが、
今回はヒープソートというのを実装してみました。
ヒープソートが実際にどういうものなのかは、
動画で観た方が分かりやすいので、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
あえて途中経過を出力させて、変化の様を追ってみました。
アルゴリズムの勉強で一度書いてみて、デバッグで追ってみるのも良いかもです。
ヒープソートのコード紹介でした。
コメント