[JavaScript 알고리즘] 정렬(Sorting) - 5. Quick Sort

Quick Sort

function quickSort(arr, left = 0, right = arr.length - 1) {
  if(left < right) {
    let pivotIndex = pivot(arr, left, right) // 3
    // left
    quickSort(arr, left, pivotIndex - 1);
    // right
    quickSort(arr, pivotIndex + 1, right);  
  }
  return arr;
}

function pivot(arr, start = 0; end = arr.length - 1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };
  
  // pivot이 항상 첫번째 요소인걸 확정합니다.
  let pivot = arr[start];
  let swapIdx = start;
  
  for(let i = start + 1, i <= end; i++) {
    if(pivot > arr[i]) {
      swapIdx++;
      swap(arr, swapIdx, i);
    }
  }
  
  // pivot을 start에서 swapPoint로 옮깁니다.
  swap(arr, start, swapIdx);
  return swapIdx;
}