クイックソート

サマリ

分割征服アルゴリズム.
1つの配列を基準として、2つの部分に分割され、1つの部分はpivotより小さく、もう1つの部分はpivotより大きく、その後、各部分を分割してソートし続けます.

マージソートと同様に分割征服アルゴリズムがベースであるが,マージソートは1つのリストを半分に分割して分割征服を行い,クイックソートはpivotの値に基づいてpivotを基準に区分され,pivotの長さが異なる可能性があるため不均一である.

一般的に、クイックソートはマージソートよりも速いです.

プロセス

時間の複雑さ

Best Case: O(n log n)

で与えられたデータ(n)を完全に分割する前に、logn個の呼び出しが生成される.

並べ替え自体に要する時間はn

である.

,n*logn

Worst Case: O(n^2)

並べ替えが完了した配列がある場合、不均衡に区分が継続されるため、n^2である.

を改善するために、ピボットを他の位置に引き抜くことができますが、100%防止することはできませんので、O(n^2)が許可されていない場合は、他のソート方法を選択する必要があります.

くうかんふくざつさ

O(logn)

長所

時間複雑度O(nlogn)の他の並べ替えアルゴリズムの中で最も速い.

アレイでスワップするため、他のメモリ領域のその場ソートは必要ありません.

短所

不安定なソート.

配列では、実行時間が長い.

コード実装

const pivot = (arr, start = 0, end = arr.length - 1) => {
  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  let pivot = arr[start]; // 가장 왼쪽을 기준으로 함
  let pivotIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      pivotIdx++;
      swap(arr, pivotIdx, i);
    }
  }
  swap(arr, start, pivotIdx);

  return pivotIdx;
};

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    // pivot은 고정이기 때문에 pivot에 -1, +1
    quickSort(arr, left, pivotIdx - 1); // left
    quickSort(arr, pivotIdx + 1, right); // right
  }
  return arr;
};