私はごく最近学びましquicksortた。ピボット選択が全体的なパフォーマンスに非常に重要な役割を果たすことを読みました。ピボット選択の 3 つのバリエーションをテストすることになっていた割り当てがありました -ランダム化、3 つの中央値、さまざまな入力サイズでの中央値の中央値。中央値バージョンの中央値は、最悪の場合でも O(n2) で実行されないことを読みました。しかし、私の結果では、ランダム化された 3 つのバージョンの中央値はほぼ同様の結果を示し、3 つのバージョンの中央値はわずかに優れていましたが、中央値の中央値は数桁も非常に貧弱でした。たとえば、入力サイズが 50000 の場合、ランダム化されたバージョンが実行され16547 us、中央値の中央値が実行されました。1139168 us. 誰かがなぜこれが起こっているのか説明できますか? （私が知る限り、ピボット選択アルゴリズムを正しく実装しました。配列を5つのセットに分割し、各セットの中央値を取得し、中央値が得られるまでこれを再帰的に繰り返します。）私は何か間違っていますか？
編集: 念のためコードを再チェックしていますが、中央値の実装の中央値が他の 2 つの実装と同じくらい遅く動作するか、(ほんのわずかに) 遅く動作するのは正常ですか? それとも、はるかに高速に動作することが保証されていますか?
Edit2:これは、中央値の中央値を見つけるために使用するコードです。見つかった値は、クイックソート関数に返され、ピボットとして使用されます。このコードはすべての適切なコーディング プラクティスに違反していると確信しています。
int getpivot(int arr[], int low, int high) {
int i,j,k,l,val,med[MAX/4],temp[6],pivot,mi,index,temp2;
if(high-low+1<=5) { //returns median if size of array<=5
for(i=1;i<=high;i++) {
val=arr[i];
j=i-1;
while(j>=0 && val<arr[j]) {
arr[j+1]=arr[j];
j--;
}
arr[j+1]=val;
}
return arr[(low+high)/2];
}
mi=0;
// divide array into groups of 5,
//finds median of those groups by insertion sorting
//adds these medians to med array
for(i=low;i+5<=high;) {
index=0;
for(j=i;j<i+5;j++)
temp[index++]=arr[j];
i+=5;
for(k=1;k<5;k++) {
val=temp[k];
l=k-1;
while(l>=0 && temp[l]>val) {
temp[l+1]=temp[l];
l--;
}
temp[l+1]=val;
}
med[mi++]=temp[2];
}
//choose random index as pivot and partition the med array
pivot=rand()%mi;
i=low=0;
j=high=mi-1;
while(i<j) {
while(i<high && med[i]<=med[pivot]) i++;
while(med[j]>med[pivot]) j--;
if(i<j) {
temp2=med[i];
med[i]=med[j];
med[j]=temp2;
}
}
temp2=med[j];
med[j]=med[pivot];
med[pivot]=temp2;
//j is final position of pivot
//see if j is left/right or equal to the position of true median of median
// and recurse accordingly
low/=5;
high/=5;
if(j==(low+high)/2) return med[j];
else if(j<(low+high)/2) return getpivot(med,j+1,high);
else return getpivot(med,low,j-1);
}