特定のソートアルゴリズムを実装すると、Googleが助けたくないという問題に遭遇しました...最初にアルゴリズムに関するいくつかの言葉：
ライオンズシェアとは、入力 (配列) を 3 つの部分に分割することです: 2 つの重要な数字 (赤と青、赤 <= 青をアサート) を選択すると、分割の要素は (1) 両方よりも少なくなり、(2) のどこかになります。と (3) ピボットの両方より大きい。これはうまく機能する部分です！
配列のソートは再帰的に行う必要があります。パーティションを分割する前に任意のピボットを使用して入力を分割し、定義ごとにソートされた長さ 1 または 2 のパーティクルになります。というか、非常に簡単にソートできます。
問題は、1 つのキー値で構成される長さ >= 3 のパーティションです。再度パーティション化すると、選択されたピボットに関係なく、すべての要素が後で同じパーティションに配置され、最終的にスタック オーバーフローが発生します。だからこそ、これには解決策があると確信しているので、あなたが私を助けることができると思いました.
必須の JavaCode スニペット: パーティショニング - ドイツ語のデバッグで申し訳ありません。翻訳も面倒です。IntTuple は 2 つの整数しか保持できません。ばかげたことは何もありません。
public static IntTuple partition(int[] E, int left, int right, int red, int blue){
if (red > blue) {
int v = red;
red = blue;
blue = v;
}
System.out.println("Partition Eingabe: " + Arrays.toString(E) + " Links=" + left + " Rechts=" + right + " Rot=" + red + " Blau=" + blue);
/*
* Es gilt r <= b, also gilt für beliebige x...
* ... x < r => x < b
* ... x > b => x > r.
*
* Das Gerüst für diesen Algorithmus wurde kopiert von Folie 7-13
*/
IntTuple result = new IntTuple (left, right); // rote und blaue Regionen sind leer
int u = left; // weiße Region ist leer, die unbekannte == E[left...right]
while (u <= result.v2) {
System.out.print("E[" + u + "]: ");
if (E[u] < red) {
System.out.print("rot ");
swap(E, result.v1, u);
result.v1++; // vergrößere die rote Region
u++; // verkleinere die unbekannte Region
} else if ((E[u] >= red) && (E[u] <= blue)) {
System.out.print("weiß ");
u++; // verkleinere die unbekannte Region
} else if (E[u] > blue) {
System.out.print("blau ");
swap(E, result.v2, u);
result.v2--; // vergrößere die blaue Region
}
System.out.print("Partition Schritt: [");
for(int i = left; i < right; i++)
System.out.print("" + E[i] + " ");
System.out.println("" + E[right] + "]");
}
System.out.print("Partition Ausgabe: [");
for(int i = left; i < right; i++)
System.out.print("" + E[i] + " ");
System.out.println("" + E[right] + "]" + " RotG=" + result.v1 + " BlauG=" + result.v2);
return result;
}
必須の JavaCode スニペット: 並べ替え
private static void flagSort(int[] E, int left, int right){
System.out.println("Sortiere: " + left + " bis " + right);
if(left < right - 1) {
Random rnd = new Random();
IntTuple v = partition(E, left, right, rnd.nextInt(50), rnd.nextInt(50));
//IntTuple v = partition(E, left, right, E[left], E[left + 1]);
flagSort(E, left, v.v1 - 1);
flagSort(E, v.v1, v.v2);
flagSort(E, v.v2 + 1, right);
} else if((left == right - 1) && (E[left] > E[right])) {
swap(E, left, right);
}
}
アイデアをお寄せいただきありがとうございます。
よろしく、LDer
もっと：私はこのハッキーで厄介な解決策を思いついた：
private static void flagSort(int[] E, int left, int right, boolean dual){
if(left < right) { // Singleton or empty segments are already sorted!
IntTuple v;
if(dual) // The last step has produced only a single white partition.
// Treat this partition with double pivot
v = partition(E, left, right, E[left], E[left]);
else // The last step has produced more than one partition, go on normally.
v = partition(E, left, right, E[left], E[left + 1]);
// Analyze partitions
if((left != v.v1) || (right != v.v2)) {
// 2 or 3 partitions available. Descend further.
flagSort(E, left, v.v1 - 1, false);
flagSort(E, v.v1, v.v2, false);
flagSort(E, v.v2 + 1, right, false);
} else if(!dual) {
// Only the white partition is not empty, partition it with double pivot
flagSort(E, v.v1, v.v2, true);
} // Last case: The only not-empty partition is white after partitioning with double pivot.
// Description of the algorithm immediately implies that this consists of only one key value, thus is sorted.
}
}
より読みやすいバージョンの作成を手伝ってくれる人はいますか?
MORE : こちらの方がずっと良く見えます:
private static void flagSort(int[] E, int left, int right, int offset){
if(left < right) { // Singleton or empty segments are already sorted!
IntTuple v = partition(E, left, right, E[left], E[left + offset]);
// Analyze partitions
if ((left != v.v1) || (right != v.v2)) {
// 2 or 3 partitions available. Descend further.
flagSort(E, left, v.v1 - 1, 1);
flagSort(E, v.v1, v.v2, 1);
flagSort(E, v.v2 + 1, right, 1);
} else if (offset > 0)
// Only the white partition is not empty, partition it with double pivot
flagSort2(E, v.v1, v.v2, 0);
// Last case: The only not-empty partition is white after partitioning with double pivot.
// Description of the algorithm immediately implies that this consists of only one key value, thus is sorted.
}
}
赤/青を明示的に渡していませんが、toto2 に感謝します。
MORE : toto2 が再び完全にポイントを持っているため、ランダム性が増します:
private static void flagSort(int[] E, int left, int right, int offset){
if(left < right) {
IntTuple v = partition(E, left, right, E[left + (offset % (right - left))],
E[left + ((2 * offset) % (right - left))]);
if ((left != v.v1) || (right != v.v2)) {
int random = rnd.nextInt(right - left);
flagSort(E, left, v.v1 - 1, random);
flagSort(E, v.v1, v.v2, random);
flagSort(E, v.v2 + 1, right, random);
} else if (offset > 0)
flagSort(E, v.v1, v.v2, 0);
}
}