quick sort
https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif
基本的な考え
以下を繰り返す
1. 適当な値を取り出す
データの先頭の要素を軸要素とする
ランダムに1つ選ぶ
ランダムに3つ選んで、その中央値を取る
左から見て最初に得られた2つの異なる値の大きいほうを取る
2. その値より小さいものを前へ、大きいものを後ろへ移動させる
3. pivotを境に2分割されたデータに対して同じことを繰り返す 実装
/icons/javascript.icon
a < bのとき-1
a > bのとき1
a === bのとき0
どっかがバグってて、無限ループに陥る
code:quickSort.js
function quickSort(array, compare = (a, b) => a - b) {
if (array.length === 2) return compare(array0, array1) < 0 ? ...array : [array1, array0]; // pivotより小さい要素を左に、pivot以上の要素を右に動かす
let i = 0;
let j = array.length - 1;
while (i < j) {
const l = compare(pivot, arrayi); const r = compare(arrayj, pivot); if (l <= 0 && r < 0) {
[resultj, resulti] = [resulti, resultj]; console.log({result});
if (i + 1 === j) break;
i++; j--;
continue;
}
if (l > 0) i++;
if (r >= 0) j--;
}
// iの位置で配列を分割し、更にソートをかける
console.log({left: result.slice(0, i), right: result.slice(i)});
return [
...quickSort(result.slice(0, i),compare),
...quickSort(result.slice(i),compare),];
}