콘텐츠로 이동

2022 01 16

2022-01-16

알고리즘 - 퀵 정렬

  1. 앞서 살펴본 선택 정렬, 버블 정렬, 삽입 정렬은 모두 O(n^2) 의 시간 복잡도를 가졌어요. 정렬하고자 하는 배열의 원소들을 순회하면서 (n번의 탐색) 배열 내의 다른 원소들과 비교하는 절차를 (또 다른 n번의 탐색) 거치기 때문인데요. O(n^2) 보다 더 효율적으로 정렬할 방법이 없을까요? 🤔 오늘 알아볼 퀵 정렬을 통해 더욱 빠르게 정렬할 수 있어요!

  2. 퀵 정렬(Quick Sort) 는 분할 정복 알고리즘을 활용한 정렬 방식이에요. 분할 정복 알고리즘이란 하나의 큰 문제를 두 개의 작은 문제로 나누고, 문제를 해결한 뒤 결과를 합치는 알고리즘을 말하는데요. 재귀적으로 자신을 호출하면서 연산의 단위를 줄여나가게 되어요. 바로 와 닿진 않을 텐데요! 퀵 정렬의 동작 방식과 예시를 보며 감을 잡아봅시다.

  3. 퀵 정렬은 다음과 같은 순서로 동작해요. - 배열의 맨 오른쪽 원소를 Pivot으로 지정한다. - Pivot 앞에는 Pivot보다 작은 원소가, Pivot 뒤에는 Pivot보다 큰 원소가 오도록 정렬한다. - Pivot보다 작은 원소가 모인 배열의 앞부분, Pivot보다 큰 원소가 모인 배열의 뒷부분에 대해 재귀적으로 해당 정렬 과정을 반복한다.
    - 정렬하고자 하는 배열에 원소가 하나밖에 없다면 재귀를 멈춘다.

    위치가 확정된 Pivot을 기준으로 배열을 앞뒤로 나누어 정렬 과정을 반복해요. 분할 정복이라는 표현이 조금 와닿나요? 예시를 보면서 조금 더 이해해봅시다! 💪

  4. 배열 [4, 5, 2, 1, 3] 을 퀵 정렬로 오름차순 정렬을 해볼게요. Pivot은 굵은 글씨로, 배열을 순회하며 크기를 비교할 원소는 언더바로 표시할게요. 또한 index라는 변수를 활용해 Pivot이 어느 위치에 들어가야 할지를 추적하는데요. index는 -1부터 시작해 Pivot보다 작은 숫자들을 발견할 때마다 1씩 증가해요. 또한 최종적으로 순회가 끝나면 index가 1 증가해 pivot의 최종 위치를 확정 지어요.

    cycle 1) [4, 5, 2, 1, 3(pivot)] 정렬하기
    [4, 5, 2, 1, 3] -> 4는 pivot 3보다 크니까 패스! (현재 index -1)
    [4, 5, 2, 1, 3] -> 5는 pivot 3보다 크니까 패스! (현재 index -1)
    [4, 5, 2, 1, 3] -> 2는 pivot 3보다 작으니까 index 자리의 4와 교환! (현재 index 0)
    [2, 5, 4, 1, 3] -> 1는 pivot 3보다 작으니까 index 자리의 5와 교환! (현재 index 1)
    [2, 1, 4, 5, 3] -> 순회 끝, pivot 3의 자리를 index 자리로 교환! (현재 index 2)
    [2, 1, 3, 4, 5] -> pivot 3의 자리가 최종으로 확정된 채로 cycle 1 종료

    cycle 2) [2, 1(pivot)] 정렬하기
    [2, 1] -> 2는 pivot 1보다 크니까 패스! (현재 index -1)
    [2, 1] -> 순회 끝, pivot 1의 자리를 index 자리로 교환! (현재 index 0)
    [1, 2] -> pivot 1의 자리가 최종으로 확정된 채로 cycle 2 종료

    cycle 3) [4, 5(pivot)] 정렬하기
    [4, 5] -> 4는 pivot 5보다 작으니까 index 자리의 4와 교환! (현재 index 0)
    [4, 5] -> 순회 끝, pivot 5의 자리를 index 자리로 교환 (현재 index 1)
    [4, 5] -> pivot 5의 자리가 최종으로 확정된 채로 cycle 3 종료

    [1, 2, 3, 4, 5] 배열 정렬 완료!

  5. 퀵 정렬은 평균적으로 O(nlog₂n) 의 시간 복잡도를 가져요. 배열을 순회하며 n번 비교하지만, 그 과정이 배열을 절반으로 분할함에 따라 log₂n번만 필요한 것이죠. 그림으로 보면 다음과 같아요.

  6. 하지만 최악의 경우, pivot이 매번 배열의 모든 원소와 크기를 비교하도록 선정된다면 O(n^2) 의 시간 복잡도를 가질 수 있어요. 배열이 오름차순/내림차순으로 정렬되어있는 경우처럼요. 따라서 퀵 정렬은 분할 정복 과정에서 배열을 절반으로 나눠줄 Pivot 선정이 매우 중요한 알고리즘이에요. 이번 뉴스레터에서는 배열의 맨 오른쪽 원소를 Pivot으로 삼았지만, 매번 랜덤하게 Pivot의 위치를 선택하는 등의 다양한 방법이 있어요! (다양한 논문들이 Pivot Selection에 대해 발표되었다고 하네요!)

코드 보러 가기