정렬: 퀵 정렬

출처: 위키백과

 

퀵 정렬이란?

퀵 정렬(Quick Sort)은 분할 정복(divide and conquer) 전략을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 분할하여 정복하는 이 방식은 대규모 데이터셋에 대해서도 빠른 정렬 속도를 제공합니다.

 

퀵 정렬의 작동 원리

퀵 정렬은 '피벗'(pivot)이라는 기준 값을 사용하여 배열을 분할합니다. 피벗보다 작은 모든 요소를 피벗의 왼쪽으로, 큰 모든 요소를 오른쪽으로 이동시킵니다. 이렇게 하여 두 부분 배열로 나눈 후 각 부분에 대해 동일한 과정을 재귀적으로 반복합니다.

 

퀵 정렬의 단계별 과정

1. 배열에서 피벗을 선택합니다(일반적으로 첫 번째 요소, 마지막 요소, 중간 요소 중 하나).
2. 피벗을 기준으로 배열을 두 부분으로 분할합니다.
3. 분할된 각 부분에 대해 퀵 정렬을 재귀적으로 적용합니다.
4. 부분 배열들이 충분히 작아질 때까지 이 과정을 반복한 후, 배열이 정렬됩니다.

퀵 정렬의 복잡도

시간 복잡도: 평균 및 최선의 경우 O(n log n), 최악의 경우 O(n^2)입니다.
공간 복잡도: O(log n)로, 재귀적 호출에 필요한 추가 메모리 공간입니다.

---

Pseudocode

function quickSort(array, low, high) {
  if (low < high) {
    pi = partition(array, low, high)
    quickSort(array, low, pi - 1)  // Left partition
    quickSort(array, pi + 1, high) // Right partition
  }
}

function partition(array, low, high) {
  pivot = array[high]
  i = (low - 1)
  for j = low to high - 1
    if (array[j] < pivot) {
      i++
      swap array[i] with array[j]
    }
  swap array[i + 1] with array[high]
  return (i + 1)
}

 

실제 예시로 이해하기

예를 들어, [33, 21, 45, 64, 55, 34, 11] 이라는 배열을 오름차순으로 정렬한다고 해봅시다. 퀵 정렬 과정은 다음과 같습니다:

1. 배열의 마지막 요소(11)를 피벗으로 선택합니다.
2. 피벗보다 작은 요소(21, 11)를 왼쪽으로, 큰 요소(33, 45, 64, 55, 34)를 오른쪽으로 분할합니다: [11, 21, 33, 45, 64, 55, 34]
3. 이제 [11, 21]과 [33, 45, 64, 55, 34]에 대해 같은 과정을 반복합니다.
4. 모든 부분 배열에 대해 정렬이 완료될 때까지 과정을 반복하면, 결과적으로 오름차순으로 정렬된 배열을 얻을 수 있습니다.

퀵 정렬은 피벗 선택에 따라 성능 차이가 발생할 수 있지만, 일반적으로 피벗을 적절히 선택하면 매우 효율적인 정렬을 수행할 수 있습니다. 이 알고리즘은 프로그래밍에서 정렬 알고리즘의 근간을 이해하는 데 도움을 줍니다.