javaでヒープソートアルゴリズムを実装するサンプル

2014年7月30日

javaコード：
import com.princeton.cs.introcs.StdIn;

public class HeapSort {

public static void sort(Comparable[] a) {
int N = a.length;
for (int k = N / 2; k >= 1; k–) {
sink(a, k, N);
}
while (N > 1) {
exch(a, 1, N–);
sink(a, 1, N);
}
}

public static void exch(Comparable[] a, int u, int v) {
Comparable temp = a[u – 1];
a[u – 1] = a[v – 1];
a[v – 1] = temp;
}

public static void sink(Comparable[] a, int k, int N) {

while (2 * k <= N) {
int j = 2 * k;
if (j < N && (a[j – 1].compareTo(a[j])) < 0) {
j++;
}
if (a[k – 1].compareTo(a[j – 1]) >= 0) {
break;
}
exch(a, k, j);
k = j;
}
}

public static void main(String[] args) {

String[] a = StdIn.readAllStrings();

for (int i = 0; i < a.length; i++)
System.out.print(a[i] + “,");
HeapSort.sort(a);

for (int i = 0; i < a.length; i++)
System.out.print(a[i] + “,");
}
}

説明：
compareTo(str) は、文字列が、str と比べて辞書的にどちらが大きいか調べます。str のほうが大きい時は負の値を、等しい時は 0を、小さい時は正の値を返します