노트

퀵 정렬

Quicksort

CS#algorithm · 연결된 개념 5개

쉽게 말하면

퀵 정렬은 아이 한 명을 기준으로 세우고 '너보다 작은 사람은 왼쪽, 큰 사람은 오른쪽'으로 나눈 뒤, 양쪽에서 또 같은 일을 하는 방식이에요. 나누고 나면 기준 아이는 이미 제자리에 서 있어서 따로 합칠 필요가 없어요.

비유가 깨지는 곳 기준을 매번 가장 작거나 큰 아이로 고르면 한쪽으로만 몰려 최악 O(n²)이 돼요. 그래서 피벗은 무작위나 세 값의 중앙값으로 골라요. 덧붙여 안정 정렬도 아니에요.

기준값(피벗, Pivot)을 하나 골라 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤, 양쪽을 다시 같은 방식으로 정렬하는 알고리즘. 나누고 나면 피벗은 최종 자리에 놓이므로 합치는 단계가 필요 없다.

function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
  if (lo >= hi) return arr
  const pivot = arr[hi]
  let p = lo
  for (let i = lo; i < hi; i++) {
    if (arr[i] < pivot) { [arr[i], arr[p]] = [arr[p], arr[i]]; p++ }
  }
  ;[arr[p], arr[hi]] = [arr[hi], arr[p]] // 피벗을 제자리에
  quickSort(arr, lo, p - 1)
  quickSort(arr, p + 1, hi)
  return arr
}
  • 평균 O(n log n), 상수가 작고 제자리 정렬(In-Place Sort)이라 실제로 빠른 편이다
  • 최악 O(n²): 피벗이 매번 최솟값이나 최댓값이면(이미 정렬된 배열에서 끝 원소를 고르면) 한쪽으로만 쏠린다. 무작위 피벗이나 세 값의 중앙값(Median of Three)으로 피한다
  • 추가 메모리는 재귀 스택만큼 평균 O(log n)
  • 안정 정렬이 아니다

평균은 병합 정렬와 비슷하지만 최악의 경우가 있다는 게 차이다. 분할 정복의 한 예이며, 다른 정렬과의 비교는 정렬 알고리즘.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 우선순위 큐

    원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

  • 빅오 표기법

    입력 크기 n이 커질 때 알고리즘의 실행 시간(시간 복잡도, Time Complexity)이나 메모리(공간 복잡도, Space Complexity)가 얼마나 빨리 늘어나는지를 대략적으로 나타내는 표기. 정확한 횟수가 아니라 증가하는 모양을 본다. 그래서 상수와 작은 항은 버린다(2n + 5는 O(n)).

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

보기 옵션