Quick Sort (퀵 정렬)

Quick Sort 란?

하나의 배열을 피벗(pivot)을 기준으로 두 개의 배열로 분할하고,(피벗을 기준으로 큰건 오른쪽, 작은건 왼쪽)

분할된 배열을 정렬한 다음, 정렬된 두 배열을 합하여 전체가 정렬된 배열이 되게 하는 정렬 알고리즘.

 

// 배열의 첫번째값을 기준(pivot)으로 잡고 왼쪽은 pivot보다 작은거, 오른쪽은 pivot보다 큰걸로 정렬
function pivot(arr, sidx = 0, eidx = arr.length - 1) {
  let pivot = arr[sidx];
  let swapIdx = sidx;

  for (let i = sidx + 1; i <= eidx; i++) {
    if (pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, swapIdx, sidx);
  return swapIdx;
}

function quickSort(arr, leftIdx = 0, rightIdx = arr.length - 1) {
  // leftIdx랑 rightIdx는 점점 가까워지다가 나중에 같아짐 -> 종료 조건
  if (leftIdx < rightIdx) {
    let pivotIdx = pivot(arr, leftIdx, rightIdx);
    quickSort(arr, leftIdx, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, rightIdx);
  }
  return arr;
}

function swap(arr, idx1, idx2) {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}
console.log(quickSort([4, 8, 2, 1, 5, 7, 6, 3]));

 

Quick Sort의 Big O

Best : n log n

Average : n log n

Worst : n^2 (이미 정렬된 경우 -> n번 분해 * n 번 비교)

+ Space Complexity : log n