퀵 정렬(Quick Sort)

피벗을 기준으로 배열을 분해 후,
각 부분을 재귀적으로 정렬하여 최종적으로 배열을 정렬하는 분할 정복 알고리즘

• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
• 병합 정렬과 달리 비균등하게 분할

진행 과정(오름차순 기준)

1. 배열에서 피벗을 선택하여 분할 기준을 설정

   → 배열을 피벗을 기준으로 두 부분으로 나눔

2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치

   → 피벗은 자신의 최종 위치에 배치된다

3. 피벗을 기준으로 왼쪽과 오른쪽 부분에 대해 각각 재귀적으로 퀵 정렬을 수행

   → 더 이상 나눠질 수 없을 때까지 반복

4. 배열이 완전히 정렬되면 최종적으로 정렬된 배열을 반환

구현 코드(오름차순 기준)

const quickSort = (arr) => {
  // 배열이 1개 이하이면 이미 정렬된 상태이므로 그대로 반환
  if (arr.length <= 1) return arr;

  // 피벗 선택 (배열의 마지막 원소를 피벗으로 선택)
  const pivot = arr[arr.length - 1];

  // 피벗을 기준으로 작은 값들은 왼쪽 배열에, 큰 값들은 오른쪽 배열에 배치
  const left = [];
  const right = [];
  
  // 피벗을 제외한 배열에서 피벗보다 작은 값은 left에, 큰 값은 right에 넣음
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot)
      left.push(arr[i]);
		else
      right.push(arr[i]);
  }

  // 재귀적으로 왼쪽과 오른쪽 배열을 정렬하고, 피벗을 합쳐서 반환
  return [...quickSort(left), pivot, ...quickSort(right)];
};

const testArr = [10, 7, 8, 9, 1, 5];
console.log(quickSort(testArr));  // [1, 5, 7, 8, 9, 10]

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선: O(n log n)
  • 평균: O(n log n)
  • 최악: O(n²)
• 공간 복잡도
  • O(log n) (재귀 호출 스택 공간)