現在、並べ替えアルゴリズムを研究しており、HeapSort と Introspective Sort を実装する必要があります。
私は HeapSort を正常に実装したと思います (コードは機能し、ランダムなサイズの何百万ものランダム配列で試し、常に機能しました)、ここに私のコードがあります:
public static <T extends Comparable<? super T>> void hsort(T[] a) {
int n = a.length;
if(n < 2) return;
/* Heapify */
for(int i = (n-2)/2; i >= 0; i--)
moveDown(a, i, n);
for(int i = n-1; i > 0; i--) {
swap(a, 0, i);
moveDown(a, 0, i);
}
}
moveDown コードは次のとおりです。
private static <T extends Comparable <? super T>> void moveDown(T[] a, int i, int max) {
T e = a[i];
int j; /* Son index */
while((j = (2*i)+1) < max) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
これらの 2 つの方法は完全に正常に動作するはずです。何度もテストしましたが、問題は発生しませんでした。
また、これらの 2 つの方法から始めて、内省的並べ替えを実装しようとしています。私のコードは次のようなものです。
public static <T extends Comparable<? super T>> void introSort(T[] a) {
int size = a.length;
if(size < 2) return;
int log = Integer.SIZE - Integer.numberOfLeadingZeros(size);
introSort(a, 0, size-1, 2*log);
}
private static <T extends Comparable<? super T>> void introSort(T[] a, int min, int max, int lev) {
if(max - min < ISORT_THRESHOLD) isort(a, min, max); // Small intervall
else if(lev == 0) hsortAux(a, min, max); // HeapSort on Array Portion
else {
// QuickSort
while (min < max) {
lev--;
/* Tukey approximation */
int t = tukeyApproximation(a, min, max-1);
//t = min; Ignore this for now and read below this code
T p = a[t];
int i = min, j = max;
do {
while(a[i].compareTo(p) < 0) i++;
while(a[j].compareTo(p) > 0) j--;
if(i <= j) {
swap(a, i, j);
i++; j--;
}
} while(i <= j);
introSort(a, min, j, lev);
min = i;
}
}
}
メソッド isort と hsortAux が正常に機能すると仮定すると、上記のコードも問題ないと思います。私のテストでは、ヒープソートが呼び出されたときにのみ失敗することに気付きました。tukey 近似を使用してピボット インデックスを決定する場合と、たとえば常に配列の最初の要素のようなランダム ピボットを選択する場合の両方で、コードは機能するはずです (ターゲットはそれを機能させることです)。私は多くのクイックソートの実装を試しましたが、それらはすべて機能し、すでに述べたように、コードはヒープソートが呼び出されていないときに機能するため、クイックソートを使用したパーティショニングは正しいはずです。パーティショニングは、実際には完全に機能する別の方法でのクイックソートからのコピーペーストです。
メソッド isort と tukeyApproximation が意図したとおりに機能することは確かです。なぜなら、それらを単独でクイックソートの実装でテストし、問題なく機能するからです。
ただし、最小値と最大値の間の配列部分でのみ機能するヒープソート (hsortAux と呼ばれるメソッド) を実装することはできないようです。こことGoogleで答えを探すのに数時間費やしました。他の人のコードを見て自分のバージョンを実装しようとしましたが、何度も失敗し、ここであなたの時間を無駄にしています:)。機能する heapSort をなんとか作成できましたが、チューキー近似によってピボットが選択されなかった場合 (たとえば、配列の最初の要素またはその部分のランダムな要素) は機能しないようでした。
元のhsortAuxから派生した現在のhsortAuxコードは次のとおりです。
private static <T extends Comparable<? super T>> void hsortAux(T[] a, int min, int max) {
for(int i = (min + max - 1)/2 ; i >= min; i--)
moveDownAux(a, min, i, max+1);
for(int i = max; i > min; i--) {
swap(a, min, i);
moveDownAux(a, min, min, i);
}
}
moveDownAux は、配列部分でのみ機能する moveDown メソッドであるはずですが、実装方法がまったくわかりません。代わりに以前の moveDown メソッドを使用しようとしましたが、明らかにまったく機能しません。moveDownAux を実装するとき、minという変数が必要かどうかさえわかりません。
これが私の現在の moveDownAux メソッドです:
private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
T e = a[i];
int j; /* Son */
while((j = (2*i)+1) < max-1) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest Son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
お時間とご回答ありがとうございます。