[자료구조] 퀵 정렬이란?

오늘은 퀵정렬에 대해서 알아보려고 합니다.

선택, 삽입, 퀵 정렬 중에서 퀵 정렬이 가장 많이 사용되는 알고리즘입니다.

 

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

 

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다.

 

쿽 정렬에서는 피벗이 사용되는데, 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피펏이라고 표현합니다.

 

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 합니다.

 

퀵 정렬 분할 방식 중에서 호어 분할 방식(Hoare Partition Scheme)을 사용하면서 리스트를 두 부분으로 나누고, 각 부분을 재귀적으로 정렬합니다. 

 

아래는 주어진 리스트를 사용하여 퀵 정렬을 진행하는 과정을 표로 나타낸 것입니다.

원래 리스트: [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

단계	현재 리스트	피벗	왼쪽 부분	오른쪽 부분
초기	[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]	피벗: 7	[]	[]
1단계	[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]		[5, 0, 3, 1, 6, 2, 4]	[9, 8]
2단계	[5, 0, 3, 1, 6, 2, 4, 7, 8]	피벗: 5	[0, 3, 1, 2, 4]	[6, 7, 9, 8]
3단계	[5, 0, 3, 1, 2, 4, 7, 6, 8, 9]		[0, 3, 1, 2, 4]	[6, 7, 8, 9]
4단계	[0, 3, 1, 2, 4, 5, 7, 6, 8, 9]	피벗: 0	[1, 2, 4]	[3, 5, 7, 6, 8, 9]
5단계	[0, 1, 2, 4, 3, 5, 7, 6, 8, 9]		[1, 2, 4]	[3, 5, 7, 6, 8, 9]
6단계	[1, 2, 4, 3, 0, 5, 7, 6, 8, 9]	피벗: 1	[0]	[2, 4, 3, 5, 7, 6, 8, 9]
7단계	[1, 0, 2, 4, 3, 5, 7, 6, 8, 9]		[0]	[2, 4, 3, 5, 7, 6, 8, 9]
8단계	[0, 1, 2, 4, 3, 5, 7, 6, 8, 9]	피벗: 2	[]	[4, 3, 5, 7, 6, 8, 9]
9단계	[0, 1, 2, 4, 3, 5, 7, 6, 8, 9]		[]	[4, 3, 5, 7, 6, 8, 9]
10단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]	피벗: 3	[]	[4, 5, 7, 6, 8, 9]
11단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]		[]	[4, 5, 7, 6, 8, 9]
12단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]	피벗: 4	[]	[5, 7, 6, 8, 9]
13단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]		[]	[5, 7, 6, 8, 9]
14단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]	피벗: 5	[]	[7, 6, 8, 9]
15단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]		[]	[7, 6, 8, 9]
16단계	[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]	피벗: 6	[]	[7, 8, 9]
17단계	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]		[]	[7, 8, 9]
18단계	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	피벗: 7	[]	[8]
19단계	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]		[]	[8]
20단계	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]		[]	[]

 

퀵 정렬은 리스트를 분할하고 재귀적으로 정렬하는 과정을 반복하여 정렬을 수행합니다. 

 

위의 표에서 굵게 표시된 원소는 각 단계에서 선택된 피벗(pivot)을 나타냅니다.

 

리스트는 피벗을 기준으로 두 부분으로 나누어지며, 각 부분은 재귀적으로 정렬됩니다.

 

이러한 과정을 통해 리스트가 정렬됩니다.

 

소스 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 퀵 정렬 함수 정의: 배열, 시작 인덱스(start), 끝 인덱스(end)를 매개변수로 받습니다.
def quick_sort(array, start, end):
    # 종료 조건: 시작 인덱스가 끝 인덱스보다 크거나 같으면 함수를 종료합니다.
    if start >= end:
        return
    # 피벗을 첫 번째 원소로 선택합니다.
    pivot = start
    left = start + 1
    right = end

    # left 포인터가 right 포인터보다 작거나 같을 때까지 반복합니다.
    while left <= right:
        # left 포인터를 오른쪽으로 이동하며 피벗보다 작거나 같은 원소를 찾습니다.
        while left <= end and array[left] <= array[pivot]:
            left += 1

        # right 포인터를 왼쪽으로 이동하며 피벗보다 큰 원소를 찾습니다.
        while right > start and array[right] >= array[pivot]:
            right -= 1

        # 만약 left 포인터가 right 포인터를 지나쳤다면 피벗과 right 위치의 원소를 교환합니다.
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            # 그렇지 않으면 left 위치의 원소와 right 위치의 원소를 교환합니다.
            array[left], array[right] = array[right], array[left]
    
    # 피벗을 기준으로 분할된 왼쪽 부분과 오른쪽 부분을 각각 재귀적으로 정렬합니다.
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

# 퀵 정렬 함수를 호출하여 배열을 정렬합니다. 시작 인덱스는 0, 끝 인덱스는 배열 길이 - 1로 지정합니다.
quick_sort(array, 0, len(array) - 1)

# 정렬된 배열을 출력합니다.
print(array)

 

파이썬의 장점을 살핀 퀵 정렬 소스코드

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)


array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 11, 15, 13, 10, 12, 14, 19, 16, 18, 17]
result = quick_sort(array)
print(result)