[알고리즘 with JS] 퀵 정렬 (quick sort)

퀵 정렬은 재귀를 통해 해결하기 가장 쉬운 방식 중 하나로 
배열 길이가 0~1까지 분할하여 개별적으로 정렬되는 방식이다.

 

퀵 정렬은 pivot이라 부르는 단일 요소를 선택하여 수행하는 것이 특징으로,
pivot보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 옮기는 과정 반복하며 정렬해 나아간다.

 

아래는 배열이 주어지면 pivot을 정해 배열 속 요소를 재배치하는 함수이다.

매개변수로 배열, 시작 인덱스, 끝 인덱스를 받으며
pivot idx를 반환해 준다.

// 배열이 주어지면 요소를 pivot으로 지정하여 배열 속 요소를 재배치하는 함수
function pivot(arr, start=0, end=arr.length-1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
  
  let pivot = arr[start]; // 시작 값을 pivot으로 지정
  let swapIdx = start;  // 반환할 pivot idx
  // pivot보다 작은 수와 큰 수를 나눔
  for (let i=start+1; i<arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++; 
      swap(arr, swapIdx, i);
    }
  }
  swap(arr, start, swapIdx);
  return swapIdx;
}

복잡해 보일 수 있지만 swapIdx는 for 문을 돌 때 해당 배열의 요소가 pivot보다 작을 때만 증가하므로
결론적으로 배열 요소 중 pivot보다 작은 값들의 개수라고 생각하면 쉽다.

마지막 swap문은 시작 idx와 swapIdx의 값을 교환하여 배열 요소를 재배치하는 것이다.

 

pivot 함수를 사용하여 pivot idx를 반환하면,
이 pivot을 기준으로 왼쪽과 오른쪽에 재귀적으로 pivot 함수를 호출하며 퀵 정렬을 수행한다.

 

아래는 퀵 정렬의 전체 코드이다.

function pivot(arr, start=0, end=arr.length-1) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
  }
  
  let pivot = arr[start]; 
  let swapIdx = start;  

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

function quickSort(arr, left=0, right=arr.length-1) {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    quickSort(arr, left, pivotIdx-1); // pivot 기준 왼쪽 배열
    quickSort(arr, pivotIdx+1, right); // pivot 기준 오른쪽 배열
  }
  return arr;
}