クイックソート

クイックソートは、分割と征服テクニックを使用して、場所を並べ替えアルゴリズムを使用すると、それが解決する簡単で、補助データ構造を使用しないように小さな問題に問題を分解することを意味与えられたリストをソートする.
クイックソートは、ピボットであるリストから要素を選択することによって開始されます.
次に、他の要素を再配置するので、ピボットより小さい全ての要素がその左側に移動し、ピボットより大きい全ての要素が右に行く.
これをピボットの左右に繰り返す.

実装

ここでは、クイックソートを再帰的に実装します.

/**
 * swap function
 */
function swap(arr: number[], i: number, j: number) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
 * recursive function
 */
function quickSort(arr: number[], start: number, end: number) {
  // base case
  if (start >= end) return;

  // rearrange the entire array based on a pivot
  // this pointer is the middle of the array, it will be explained in the next function
  const pointer = rearrange(arr, start, end);

  // rearrange the left and right side of the pivot
  quickSort(arr, start, pointer - 1);
  quickSort(arr, pointer + 1, end);
}

/**
 * function to rearrange the array based on a pivot
 */
function rearrange(arr: number[], start: number, end: number) {
  // choose last element to be the pivot
  const pivot = arr[end];

  // this pointer works like a placeholder for the pivot, at the end, it will be in the middle of the array, and will swap with the pivot that is in the end
  let pointer = start;

  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      swap(arr, pointer, i);

      // increment pointer, so it stays ahead of the elements that are smaller than the pivot
      pointer++;
    }
  }

  // put the pivot in the middle
  swap(arr, pointer, end);
  return pointer;
}

const arr = [3, 7, 2, 6, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // 2, 3, 5, 6, 7

悪いソートの重要な部分はピボットの選択である.なぜなら、悪い選択は最悪の時間複雑性につながる.なぜなら、このアルゴリズムの平均時間複雑性は、O(n log n)であり、最悪の場合はO(N≠)であるが、このアルゴリズムのランダム化バージョンを使用することで最悪の場合を回避することができるからである.また、Merge Sortとは異なり、速いソートは、それが一定の空間複雑さo(1)を持つ利点を与えます.