5장. 정렬(1) - 퀵정렬이란?

 

 

퀵 정렬

• 피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬이라고도 불린다.
• 병렬 정렬과 마찬가리고 분할 정복 알고리즘
• 피벗이라는 개념을 통해 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝하면서 쪼개 나간다.
• 이 중에서도 로무토 파티션이란 항상 맨 오른쪽의 피벗을 택하는 단순한 방식으로, 토니 호어가 고안한 최초의 퀵 정렬 알고리즘보다 훨씬 더 간결하고 이해하기 쉽기 때문에 퀵 정렬 소개 시 항상 맨 처음에 언급됨

 

퀵 정렬 수도코드

Quicksort(A, lo, hi)
	if lo < hi then
    	pivot := partition(A, lo, hi)
        Quicksort(A, lo, pivot - 1)
        Quicksort(A, pivot + 1, hi)

 

• 기본 조건 확인: Quicksort(A, lo, hi)는 lo < hi일 때만 실행된다. 즉, 리스트에 요소가 1개 이하로 남았다면 더 이상 정렬할 필요가 없다는 뜻이다.
• 피벗 분할:
  • partition(A, lo, hi) 함수는 A[lo]부터 A[hi]까지의 구간에서 피벗을 기준으로 요소들을 나눈다.
  • 이 함수는 피벗 위치를 반환하며, 이 위치에서 피벗 왼쪽에는 피벗보다 작은 값들, 오른쪽에는 큰 값들이 오도록 분할된다.
• 재귀 호출:
  • Quicksort(A, lo, pivot - 1)을 호출하여 피벗 왼쪽 부분 리스트를 정렬한다.
  • Quicksort(A, pivot + 1, hi)을 호출하여 피벗 오른쪽 부분 리스트를 정렬한다.
  • 이 과정을 반복하면 리스트 전체가 정렬된다.

 

 

퀵 정렬 예시

예를 들어, 리스트 A = [8, 3, 1, 7, 0, 10, 2]가 있다고 가정하자. 이 리스트를 오름차순으로 정렬하는 과정은 다음과 같다.

1. 피벗 선택: 먼저 리스트의 마지막 요소인 2를 피벗으로 선택
2. 분할 과정: 피벗 2를 기준으로 리스트를 나누기 위해, 리스트 내의 요소들을 두 그룹으로 나눈다.
   • 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치하도록 한다.
   • 예를 들어 A의 요소들을 비교해보면, 0, 1은 피벗보다 작아서 왼쪽으로, 8, 3, 7, 10은 오른쪽으로 이동한다.
   • 분할 후 리스트는 [1, 0, 2, 8, 3, 10, 7]이 됩니다. 여기서 2는 피벗 위치에 고정되어 있어요.
3. 재귀 호출: 피벗을 기준으로 나눈 두 그룹 [1, 0]과 [8, 3, 10, 7]에 대해 다시 퀵 정렬을 적용한다.
   • [1, 0]의 경우, 피벗은 0이고 나머지 요소와 비교한 후 [0, 1]로 정렬된다.
   • [8, 3, 10, 7]의 경우 피벗을 7로 선택해서 나누면 [3, 7, 10, 8]로 정렬된다.
4. 최종 정렬 완료: 모든 재귀 호출이 끝나면 리스트는 [0, 1, 2, 3, 7, 8, 10]처럼 완전히 정렬된다.

 

partition 함수 예시

partition 함수의 코드도 함께 설명하면 아래와 같다. 

def partition(lo, hi):
    pivot = A[hi]  # 피벗을 마지막 요소로 설정
    left = lo      # 왼쪽 포인터 초기화

    # lo부터 hi - 1까지 순회
    for right in range(lo, hi):
        # 현재 요소가 피벗보다 작다면, 왼쪽에 배치
        if A[right] < pivot:
            A[left], A[right] = A[right], A[left]
            left += 1

    # 피벗을 올바른 위치로 이동
    A[left], A[hi] = A[hi], A[left]
    return left  # 피벗의 최종 위치 반환

• 리스트 A = [8, 3, 1, 7, 0, 10, 2]를 정렬한다고 가정해보자.
• 여기서 partition(lo, hi) 함수는 피벗을 기준으로 리스트를 나누는 작업을 수행한다.

 

코드 실행 예시

• lo = 0, hi = 6으로 partition(0, 6)을 호출한다.
• pivot = A[6] = 2이므로, 2를 피벗으로 설정한다.
• left는 lo 위치에서 시작하므로 초기값은 0이다.

 

for 루프 순회 과정

• right 포인터는 lo부터 hi-1까지 순회하면서 pivot과 값을 비교하고, 피벗보다 작은 값이 있으면 left와 교환한다.

1. right = 0: A[0] = 8은 피벗 2보다 크므로 교환하지 않고 left는 그대로이다.
2. right = 1: A[1] = 3도 피벗보다 크므로 역시 교환하지 않는다.
3. right = 2: A[2] = 1은 피벗보다 작으므로, A[left]와 A[2]를 교환한다.
   • 리스트는 [1, 3, 8, 7, 0, 10, 2]로 변하고, left는 1로 증가한다.
4. right = 3: A[3] = 7은 피벗보다 크므로 교환하지 않는다.
5. right = 4: A[4] = 0은 피벗보다 작으므로, A[left]와 A[4]를 교환한다.
   • 리스트는 [1, 0, 8, 7, 3, 10, 2]로 변하고, left는 2로 증가한다.
6. right = 5: A[5] = 10은 피벗보다 크므로 교환하지 않는다.

 

피벗 위치 이동

• for 루프가 끝난 후, A[left]와 A[hi]를 교환하여 피벗을 올바른 위치에 둔다.
• 이제 partition 함수는 left = 2를 반환한다. 이 위치는 피벗의 최종 위치이며, 이 위치를 기준으로 리스트가 나뉘어진다:
  • [1, 0]은 피벗 2보다 작은 값들
  • [7, 3, 10, 8]은 피벗 2보다 큰 값들

이렇게 partition이 완료되었으니, 이제 Quicksort를 각각의 부분 리스트에 대해 재귀적으로 호출하면 리스트 전체가 정렬된다.

 

퀵 정렬 전체 코드

def quicksort(A, lo, hi):
    def partition(lo, hi):
        pivot = A[hi]  # 피벗을 마지막 요소로 설정
        left = lo      # 왼쪽 포인터 초기화

        # lo부터 hi - 1까지 순회
        for right in range(lo, hi):
            # 현재 요소가 피벗보다 작다면, 왼쪽에 배치
            if A[right] < pivot:
                A[left], A[right] = A[right], A[left]
                left += 1

        # 피벗을 올바른 위치로 이동
        A[left], A[hi] = A[hi], A[left]
        return left  # 피벗의 최종 위치 반환
        
    if lo < hi:
    	pivot = partition(lo, hi)
        quicksort(A, lo, pivot -1)
        quicksort(A, pivot+1, hi)

 

• 퀵 정렬은 매우 빠르며 효율적인 알고리즘이지만, 최악의 경우에는 O(n^2)이 된다.
• 만약 이미 정렬된 배열이 입력값으로 들어왔다고 가정해보자. 이 경우 피벗은 계속 오른쪽에 위치하게 되므로 파티셔닝이 전혀 이뤄지지 않는다.
• 이때 n의 라운드에 거쳐 결국 전체를 비교하기 때문에, 버블 정렬과 다를 바 없는 최악의 성능을 보이게 된다.
• 항상 일정한 성능을 보이는 병합 정렬과 달리, 퀵 정렬은 이처럼 입력값에 따라 성능 편차가 심한 편이다.

 

 

안정 정렬 vs 불안정 정렬

• 퀵 정렬의 단점은 안정 정렬이 아니라는 것이다.
• 그림 1과 같이 지역별 발송 시각을 시간 순으로 정렬한 택배 발송 로그가 있다고 가정해보자.
• 안정 정렬의 경우 지역명으로 재정렬하더라도 기존 순서가 그대로 유지되는 반면, 불안정 정렬의 경우 기존의 정렬 순서는 무시된 채 모두 섞이게 된다.