Quick Sort (퀵 정렬)

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

Selection Sort (선택 정렬)

Insertion Sort (삽입 정렬)

Bubble Sort (버블 정렬)

Quick Sort (퀵 정렬)

퀵 정렬이란?

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

분할 정복이란?

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

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

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

퀵 정렬 알고리즘

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

코드

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

js의 메서드를 이용한 방식

const array = [1, 4, 2, 3, 5];
 
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 maxArray = arr.filter((item) => item > pivot);
 
  return [...quickSort(minArray), pivot, ...quickSort(maxArray)];
}
 
console.log(quickSort(array)); // [1, 2, 3, 4, 5]

js 메서드인 fillter를 이용해 중간값인 pivot을 기준으로 작은값을 모은 배열, 큰값을 모은 배열을 합치는 과정을 재귀적으로 반복합니다.

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

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