퀵정렬(QuickSort) 이론과 파이썬 구현

 퀵정렬(QuickSort)

 

퀵정렬은 리스트의 한 요소를 선택해 피벗(pivot)으로 선택합니다.

피벗은 리스트의 첫 번째 요소나 마지막 요소 혹은 아무거나 선택 가능합니다.

혹은 리스트 내의 값 중에 크기순으로 중간 값을 선택하는 경우도 있습니다.

 

피벗을 중심으로 피벗보다 작은 요소들은 왼쪽에 구성되고 피벗보다 큰 요소들은 오른쪽에 구성됩니다.

그리고 왼쪽에 있는 요소들을 가지고 피벗을 선택하고 정렬을 합니다. 마찬가지로 오른쪽에 있는 요소들도 피벗을 선택해 정렬을 합니다.

즉, 퀵정렬은 부분 리스트에 대해 순환 호출하는 식으로 실행됩니다.

더이상 부분 리스트가 분할이 불가능할 때까지 실행하면 전체를 정렬할 수 있습니다. 

 

퀵정렬은 평균적으로 빠른 수행 속도를 자랑하는 정렬 방법입니다.

하지만 리스트가 불균형하게 나눠질 경우 시간 복잡도는 나빠집니다.

 

퀵정렬을 이용한 첫번째 과정 반복 결과

 

피벗은 마지막 요소로 설정하였습니다.

 

2 < 3 이기 때문에 5와 2를 교환해줍니다.

1 < 3 이기 때문에 5와 1을 교환해줍니다.

피벗보다 작은 요소들을 왼쪽에 구성하기 위해 리스트의 앞자리부터 순서대로 교환해줍니다.

 

피벗보다 작은 요소들은 2, 1이기 때문에 다음 리스트의 값과 피벗값을 바꿔줍니다.

첫번째 과정을 통해 3은 정렬 완료 되었습니다.

 

퀵정렬을 이용한 전체 정렬 과정

 

퀵정렬의 파이썬 코드입니다.

def quick_sort(a, start, end):

    if start >= end:
        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 = i + 1
    
    a[i], a[end] = a[end], a[i]
    
    quick_sort(a, start, i - 1) # pivot보다 작은 그룹
    quick_sort(a, i + 1, end)  # pivot보다 큰 그룹

 
def quick_sorted(a):
    quick_sort(a, 0, len(a) - 1)

b = [5, 2, 4, 6, 1, 7, 3]
quick_sorted(b)

# 출력>>[1, 2, 3, 4, 5, 6, 7]
print(b)