Quick Sort (퀵 정렬)

알고리즘 포스팅 하며 복습하기 (정렬편) 📊

Selection Sort (선택 정렬)

Insertion Sort (삽입 정렬)

Bubble Sort (버블 정렬)

Quick Sort (퀵 정렬)

Merge Sort (병합 정렬)

Heap Sort (힙 정렬)

퀵 정렬이란?

퀵 정렬은 분할 정복(divide and conquer)을 이용해 데이터를 정렬하는 알고리즘입니다.

분할 정복이란?

해결할 수 없는 문제를 작은 문제들로 분할하여 해결하는 방법

Divide : 문제를 분할하여 더 작은 하위 문제로 분할이 가능할 때 까지 나누는 과정
Conquer : 하위 문제를 재귀적으로 해결하는 과정
Combine : 하위 문제의 해결 결과를 조합하여 최종 답을 도출하는 과정

퀵 정렬에서의 분할정복은 이렇습니다.

퀵 정렬 알고리즘

배열에서 하나의 요소를 선택하여 Pivot으로 선택 (보통 첫번째 요소)
Pivot을 기준으로 작은값, 큰값으로 배열을 분할 (Divide)
분할된 배열을 재귀적으로 정렬 (Conquer)
분할된 배열을 합쳐서 정렬된 배열을 반환 (Combine)

코드

두가지 방식이 있는데 하나는 자바스크립트의 메서드를 이용해 선언적으로 작성하고 하나는 실제 알고리즘에 기반한 코드입니다.

js의 메서드를 이용한 방식

const array = [1, 4, 2, 3, 5, 2];
 
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
 
  const pivot = arr[Math.floor(arr.length / 2)];
 
  const minArray = arr.filter((item) => item < pivot);
  const equalArray = arr.filter((item) => item === pivot);
  const maxArray = arr.filter((item) => item > pivot);
 
  return [...quickSort(minArray), ...equalArray, ...quickSort(maxArray)];
}
 
console.log(quickSort(array)); // [1, 2, 2, 3, 4, 5]

js 메서드인 filter를 이용해 가운데 위치의 값을 pivot으로 잡고, 작은값을 모은 배열과 큰값을 모은 배열을 합치는 과정을 재귀적으로 반복합니다.

pivot과 같은 값을 모으는 배열이 따로 필요합니다. <와 >로만 나누면 pivot과 값이 같은 요소들이 양쪽 어디에도 들어가지 못하는데, 마지막에 pivot 하나만 끼워 넣으면 나머지가 사라지기 때문입니다. [2, 2, 1]을 넣으면 [1, 2]가 나오는 식입니다.

실제 알고리즘에 기반한 코드

const array = [1, 4, 2, 3, 5, 10, -5];
 
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 배열의 길이가 1 이하이거나 left가 right보다 크거나 같으면 이미 정렬된 상태이므로 반환
  if (arr.length <= 1 || left >= right) {
    return arr;
  }
 
  // 랜덤한 피벗 인덱스를 선택하여 최악의 경우 성능 저하 방지
  const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  const pivotValue = arr[pivotIndex];
 
  // 피벗을 기준으로 작은 값과 큰 값을 찾기 위한 두 개의 포인터 설정
  let minTarget = left;
  let maxTarget = right;
 
  // 두 포인터가 서로 교차할 때까지 반복
  while (minTarget <= maxTarget) {
 
    // 피벗 이상인 값을 만날 때까지 minTarget 포인터를 오른쪽으로 이동
    while (arr[minTarget] < pivotValue) {
      minTarget++;
    }
 
    // 피벗 이하인 값을 만날 때까지 maxTarget 포인터를 왼쪽으로 이동
    while (arr[maxTarget] > pivotValue) {
      maxTarget--;
    }
    
    // 두 포인터가 교차하지 않았다면 값을 교환(swap)
    if (minTarget <= maxTarget) {
      // 같은 요소끼리의 불필요한 swap 방지
      if(minTarget !== maxTarget) {
        [arr[minTarget], arr[maxTarget]] = [arr[maxTarget], arr[minTarget]];
      }
 
      // 포인터 이동
      minTarget++;
      maxTarget--;
    }
  }
 
  // 피벗 기준 왼쪽 부분 배열을 재귀적으로 정렬
  if (left < maxTarget) {
    quickSort(arr, left, maxTarget);
  }
 
  // 피벗 기준 오른쪽 부분 배열을 재귀적으로 정렬
  if (right > minTarget) {
    quickSort(arr, minTarget, right);
  }
 
  // 최종적으로 정렬된 배열 반환
  return arr;
}
 
console.log(quickSort(array)); // [-5, 1, 2, 3, 4, 5, 10]

두 포인터를 이동시키는 조건이 <, > 라서 pivot과 값이 같은 요소를 만나면 멈춥니다. 그 자리에서 교환이 일어나기 때문에 같은 값들이 양쪽으로 나뉘어 흩어지고, 덕분에 중복이 많은 배열에서도 분할이 한쪽으로 쏠리지 않습니다.

시간 복잡도

퀵 정렬은 pivot을 선택할 때 최소 또는 최대값을 선택할 경우 분할이 한쪽으로 치우치게 되어 시간 복잡도가 최악이 됩니다.
평균적으로는 O(nlogn)을 반환 하는 경우가 많지만 최악을 고려하여 시간 복잡도는 O(n^2) 입니다.
Big O 표기법은 최악의 경우를 기준으로 표기