Edited at

ズルをして、「とても長い配列の上位M件だけをクイックソートより高速に取り出す」

More than 3 years have passed since last update.

とても長い配列の上位M件だけをクイックソートより高速に取り出すの計測用コードを見て、ズルをしたら微妙に早くなるんじゃないかと思って試したら3倍くらい早くなりました。

なお、ズルなので実用的ではありません。


計測結果

60回平均で3倍速。

test: 1

test: 2
...
test: 59
test: 60
QuickTopSort: 18.2989166666521ms
CheatSort: 5.20891666669243ms


ズルの内容

入力データが一様分布であることから上位M件とそれ以外の下位を分離する値を大まかに予想し、最初のピポッドに使っています。


実装

元のquickTopSortのコードをコピペして次のように変えました。

修正済:なお、元のコードの if (from + 1 >= to) return;if (from >= to) return; が正しいのではないかと思われます(quickSort([2,1])を実行してみる限り)。

function cheatSort(arr, M, p) {

arr = arr.slice(0);
cheatSortCore(arr, M, p);
return arr;
}

function cheatSortCore(arr, M, p) {
var i = 0,
j = arr.length - 1,
tmp;

if (arr.length < 2) return arr;

while (true) {
while (arr[i] < p && i <= j) i++;
while (arr[j] >= p && i <= j) j--;

if (i >= j) {break;}
else {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}

quickTopSortCore(arr, M, 0, i - 1);
if (i - 1 < M) quickTopSortCore(arr, M, i, arr.length - 1);
}

function test3() {
var a = 0,
b = 1e9,
p = 2 * M * (b - a) / N + a;
res3 = cheatSort(arr, M, p);
}