입문 - 퀵정렬

앞서 병합 정렬로 줄 세우기는 학생들을 일단 두 그룹으로 나눠 각각 병합 정렬을 한 후, 정렬된 두 그룹에 있는 학생들의 키를 다시 비교하여 한 줄로 합치는(병합) 과정이었습니다.

이번에 배울 퀵 정렬(Quicksort)은 ‘그룹을 둘로 나눠 재귀 호출’하는 방식은 병합 정렬과 같지만, 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다릅니다. 즉, 먼저 기준과 비교해서 그룹을 나눈 다음 각각 재귀 호출하여 합치는 방식입니다.

퀵 정렬로 줄 세우기

1 | 학생들에게 일일이 지시하는 것이 귀찮아진 선생님은 학생들이 알아서 줄을 서는 방법이 없을지 고민입니다. 그렇다고 열 명이나 되는 학생들에게 한 번에 알아서 줄을 서라고 하면 소란스러울 것 같아 조를 나누려고 합니다.

2 | 열 명 중에 기준이 될 사람을 한 명 뽑습니다. 기준으로 뽑은 태호를 줄 가운데 세운 다음 태호보다 키가 작은 학생은 태호 앞에, 태호보다 큰 학생은 태호 뒤에 서게 합니다(학생들은 태호하고만 키를 비교하면 됩니다).

3 | 기준인 태호는 가만히 있고, 태호보다 키가 작은 학생은 작은 학생들끼리, 큰 학생은 큰 학생들끼리 다시 키 순서대로 줄을 서면 줄 서기가 끝납니다.

쉽게 설명한 퀵 정렬 알고리즘

Pivot을 기준으로 좌우로 나누는 것을 Partitioning

# 쉽게 설명한 퀵 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
 
def quick_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
    if n <= 1:
        return a
    # 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정
    pivot = a[-1]  # 편의상 리스트의 마지막 값을 기준 값으로 정함
    g1 = []        # 그룹 1: 기준 값보다 작은 값을 담을 리스트
    g2 = []        # 그룹 2: 기준 값보다 큰 값을 담을 리스트
    for i in range(0, n - 1):  # 마지막 값은 기준 값이므로 제외
        if a[i] < pivot:       # 기준 값과 비교
            g1.append(a[i])    # 작으면 g1에 추가
        else:
            g2.append(a[i])    # 크면 g2에 추가
    # 각 그룹에 대해 재귀 호출로 퀵 정렬을 한 후
    # 기준 값과 합쳐 하나의 리스트로 결괏값 반환
    return quick_sort(g1) + [pivot] + quick_sort(g2)
 
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))

• 실행결과

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

리스트 [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]를 퀵 정렬하는 과정

① 리스트에서 기준 값을 하나 정합니다. 이 책에서는 편의상 정렬할 리스트의 맨 마지막 값을 기준 값으로 정하였습니다.

[6 8 3 9 10 1 2 4 7 5]의 기준 값: 5

② 기준 값보다 작은 값을 저장할 리스트로 g1, 큰 값을 저장할 리스트로 g2를 만듭니다.

③ 리스트에 있는 자료들을 기준 값인 5와 차례로 비교하여 5보다 작은 값은 g1, 큰 값은 g2에 넣습니다. 예를 들어 6은 5보다 크므로 g2에 넣고, 그 다음 값인 8도 5보다 크므로 g2, 3은 5보다 작으므로 g1에 넣습니다.

g1: [3 1 2 4]
g2: [6 8 9 10 7]

④ 재귀 호출을 이용하여 g1을 정렬합니다. 함수 안에서 퀵 정렬을 재귀 호출하면서 문제를 풀어 [1 2 3 4]를 결과로 돌려줍니다.

⑤ 재귀 호출을 이용하여 g2를 정렬합니다. 마찬가지로 퀵 정렬로 문제를 풀어 [6 7 8 9 10]을 결과로 돌려줍니다.

⑥ 이제 g1에는‘기준보다 작은 값들’이 정렬되어 있고 g2에는‘기준보다 큰 값들’이 정렬되어 있습니다. 따라서 g1, 기준 값, g2를 순서대로 이어 붙이면 정렬이 완료됩니다.

[1 2 3 4] + [5] + [6 7 8 9 10] → [1 2 3 4 5 6 7 8 9 10]

⑦ 최종 결과: [1 2 3 4 5 6 7 8 9 10]

알아보기

퀵 정렬 함수 quick_sort()는 재귀 호출 함수이므로 병합 정렬과 마찬가지로 첫 부분에 종료 조건이 명시되어 있습니다.

먼저 입력으로 주어진 리스트 a의 크기가 1 이하이면, 즉 자료가 한 개뿐이거나 아예 비어 있다면 정렬할 필요가 없으므로 입력 리스트를 그대로 돌려주면서 재귀 호출을 끝냅니다.

n = len(a)
if n <= 1:
    return a

또한, 퀵 정렬에서는 그룹을 나누기 위한 기준 값( pivot)이 필요합니다. 프로그램에서는 편의상 주어진 리스트의 맨 마지막 값을 기준 값으로 사용하였습니다.

pivot = a[-1]

다음 문장은 g1을 퀵 정렬한 결과에 기준 값과 g2를 퀵 정렬한 결과를 이어 붙여 새로운 리스트를 만들어 돌려주는 문장입니다.

return quick_sort(g1) + [pivot] + quick_sort(g2)

퀵 정렬의 일반화

퀵 정렬의 실제 구현(partition)은 매번 새로운 메모리 할당 없이 값의 교환(swap)을 이용해서 구현된다.

일반적인 퀵 정렬 알고리즘

쉽게 설명한 퀵 정렬 프로그램은 새로운 리스트 g1과 g2를 만들어 값을 분류하고, 결과 리스트도 새로 만들어 돌려줍니다. 이번에는 입력 리스트 안에서 직접 위치를 바꾸면서 정렬하는 일반적인 퀵 정렬을 살펴보겠습니다.

# 퀵 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
# 리스트 a에서 어디부터(start) 어디까지(end)가 정렬 대상인지
# 범위를 지정하여 정렬하는 재귀 호출 함수
def quick_sort_sub(a, start, end):
    # 종료 조건: 정렬 대상이 한 개 이하이면 정렬할 필요가 없음
    if end - start <= 0:
        return
    # 기준 값을 정하고 기준 값에 맞춰 리스트 안에서 각 자료의 위치를 맞춤
    # [기준 값보다 작은 값들, 기준 값, 기준 값보다 큰 값들]
    pivot = a[end]   # 편의상 리스트의 마지막 값을 기준 값으로 정함
    i = start
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[end] = a[end], a[i]
    # 재귀 호출 부분
    quick_sort_sub(a, start, i - 1) # 기준 값보다 작은 그룹을 재귀 호출로 다시 정렬
    quick_sort_sub(a, i + 1, end)  # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬
 
# 리스트 전체(0 ~ len(a) -1)를 대상으로 재귀 호출 함수 호출
def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)
 
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)

• 실행결과

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

기준 값의 중요성

줄 세우기에서 선생님이 기준으로 정한 학생이 하필이면 열 명 중 키가 가장 작은 학생이었다면 어떻게 될까요? 안타깝게도 기준보다 작은 그룹(g1)에는 학생이 한 명도 없고, 기준보다 큰 그룹(g2)에는 나머지 학생이 모두 모인 상황이 됩니다. 이렇게 되면 그룹을 둘로 나눈 의미가 없어져 퀵 정렬의 효율이 낮아집니다.

따라서 퀵 정렬에서는 ‘좋은 기준’을 정하는 것이 정렬의 효율성을 가늠하므로 굉장히 중요합니다. 다만, 좋은 기준을 정하는 방법은 어려운 내용이므로 예제 프로그램에서는 간단히 자료의 마지막 값을 기준 값으로 사용하였다.

알고리즘 분석

퀵 정렬의 계산 복잡도는 최악의 경우 선택 정렬이나 삽입 정렬과 같은 O(n제곱)이지만, 평균적일 때는 병합 정렬과 같은 O(n·logn)입니다.

최악의 경우란 기준을 잘못 정하여 그룹이 제대로 나뉘지 않았을 때입니다. 하지만 다행히도 좋은 기준 값을 정하는 알고리즘에 관해서는 이미 많이 연구가 되어 있기 때문에 퀵 정렬은 대부분의 경우 O(n·logn)으로 정렬을 마칠 수 있습니다.