Quick sort

平均計算時間: O(n \log n)

不安定ソート

JavaScriptによる実装

function partition(a, begin, end) {
  let pValue = a[end - 1];
  let pivot = begin;

  for (let i = begin; i < end - 1; i++) {
    if (a[i] <= pValue) {
      [a[pivot], a[i]] = [a[i], a[pivot]];
      pivot++;
    }
  }

  [a[pivot], a[end - 1]] = [a[end - 1], a[pivot]];
  return pivot;
}

function quickSort(a, begin = 0, end = a.length) {
  if (begin < end - 1) {
    const pivot = partition(a, begin, end);
    quickSort(a, begin, pivot);
    quickSort(a, pivot, end);
  }
}

const a = [7, 15, 1, 8, 11, 5, 13, 0, 2, 4, 6, 3, 12, 14, 9, 10];
quickSort(a);

console.log(a);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]