私はプログラミングにかなり慣れていないので、3分割の中央値と3のカットオフを使用したクイックソートアルゴリズムの視覚的表現を希望します。
Javaアルゴリズムは理解しにくいため、反復プロセス全体を確認したいと思います。
たとえば、この配列にクイックソートを適用してみてください：[2、6、3、1、6、5、2、4、8]
3の中央値ルールでは、ピボットは左端、中央、および右端の要素の中央値です。したがって、2、6、および8の中央値は6です。
回答：
回答№1の場合は3次のステップはパーティション分割です： ピボットを選択したら、ピボットよりも小さい要素をすべて左に移動し、大きい要素をすべて右に移動します。これが完了すると、左側と右側を別々にソートできます。
パーティション化する前に：
[2,6,3,1,6,5,2,4,8]
分割後 <6 左に、 >=6 右側に：
[2,3,1,5,2,4] [6,6,8]
左右に並べ替えるには、両側で同じ手順を繰り返します。
パーティション化手順の詳細を説明します（実際の手順では、要素の順序は異なります）。
覚えておくべき問題：
分割後、どちらかの側に少なくとも1つの要素が残っている必要があります。そうでない場合、プロシージャは永久にループする可能性があります（さらに悪いことに、残っている要素はピボットになります）。
理想的には、パーティショニングは配列を2つに分割しますほぼ同じサイズのサブアレイ。しかし、非常に不均等なサイズも発生する可能性があり、アルゴリズムが非常に遅くなります。 3の中央値のヒューリスティックは、この現象を完全には回避しません。
アルゴリズムは再帰的に書かれています（ソート関数はそれ自体を呼び出します）。 2つのサブ配列を並べ替えるときは、ネストされた呼び出しの数が最小化されるように、最小のものから始めます。これは重要;
小さな配列では手順がやり過ぎです。この場合、StraightInsertionやStraightSelectionなどのより単純なメソッドに切り替えることをお勧めします。
ソートプロセス全体を、ノードが配列を保持し、ピボットが区別され、サブ配列を保持する2人の息子を持つバイナリツリーとしてスケッチできます。
回答№2については2
それで、2,6,8の媒体は6です。
次のステップは、配列を左半分には6未満の要素が含まれ、右半分には6以上の要素が含まれます。その後、各半分でquicksortを呼び出します。
次のJavaプログラムはクイックソートを実装し、ソートの前後に各サブ配列を表示します。中央値の選択も表示されます。
import java.io.*;
public class Quicksort {
void swap(int[] data, int i, int j) {
int t = data[i];
data[i] = data[j];
data[j] = t;
}
void display(int[] data, int left, int right) {
for (int i = 0; i < right; ++i) {
System.out.print(i < left ? " " : " "+data[i]);
}
System.out.println();
}
//--- in-place implementation with median-of-three pivot
int quicksort(int[] data, int left, int right, int callId) {
int saveCallId = callId;
System.out.print(callId+". sorting:");
display(data, left, right);
if (left+1 >= right) {
System.out.print(" "+saveCallId+". result:");
display(data, left, right);
return callId;
}
int ai = left, bi = (left+right)/2, ci = right-1, pos;
int a = data[ai], b = data[bi], c = data[ci];
if (a < b) {
if (c < a) {
pos = ai;
} else if (c < b) {
pos = ci;
} else {
pos = bi;
}
} else {
if (c < b) {
pos = bi;
} else if (c < a) {
pos = ci;
} else {
pos = ai;
}
}
int pivot = data[pos];
System.out.println(" median of ["+a+", "+b+", "+c+"] is "+pivot);
swap(data, right-1, pos);
int tail = left;
for (int i = left; i != right-1; ++i) {
if (data[i] < pivot) {
swap(data, tail, i);
++tail;
}
}
swap(data, right-1, tail);
callId = quicksort(data, left, tail, ++callId);
callId = quicksort(data, tail+1, right, ++callId);
System.out.print(" "+saveCallId+". result:");
display(data, left, right);
return callId;
}
public static void main(String[] args) {
int[] data = new int[]{ 2, 6, 3, 1, 6, 5, 2, 4, 8 };
new Quicksort().quicksort(data, 0, data.length, 0);
}
}
入力の場合 { 2, 6, 3, 1, 6, 5, 2, 4, 8 }、出力は次のようになります。
0. sorting: 2 6 3 1 6 5 2 4 8
median of [2, 6, 8] is 6
1. sorting: 2 3 1 5 2 4
median of [2, 5, 4] is 4
2. sorting: 2 3 1 2
median of [2, 1, 2] is 2
3. sorting: 1
3. result: 1
4. sorting: 2 3
median of [2, 3, 3] is 3
5. sorting: 2
5. result: 2
6. sorting:
6. result:
4. result: 2 3
2. result: 1 2 2 3
7. sorting: 5
7. result: 5
1. result: 1 2 2 3 4 5
8. sorting: 6 8
median of [6, 8, 8] is 8
9. sorting: 6
9. result: 6
10. sorting:
10. result:
8. result: 6 8
0. result: 1 2 2 3 4 5 6 6 8
回答№3の場合は0
インタラクティブな視覚化を見て、それで遊ぶことができます クルミ。ダイクストラ分割（ピボットよりも小さい、等しい、大きい）を使用します。