퀵 정렬

요약

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
  • 분할 정복(divide and conquer)이란?
    • 문제를 작은 문제로 분리하고 각각을 해결한 다음,결과를 모아서 원래의 문제를 해결
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 과정
  • 리스트 안에 있는 한 요소를 선택한다. 피벗(pivot) 이라고 한다.
  • 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
  • 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
    • 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
    • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
  • 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
    • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

코드

퀵 정렬은 데이터를 분할하는 과정과 정렬하는 과정으로 나뉘어진다.
아래의 코드는 partition() 함수와 quick_sort()함수로 구성되어있으며,
partition() 함수는 pivot을 기준으로 정렬을, quick_sort()함수는 분할을 담당한다.

def partition(arr, left, right):
    low = left
    high = right+1
    pivot = arr[left]
    
    while True:
        while True: #pivot의 왼쪽 리스트 중에 pivot보다 큰 요소 찾기
            low += 1

            condition = low <= right and arr[low] < pivot
            if not condition:
                break

        while True: #pivot의 오른쪽 리스트 중에 pivot보다 작은 요소 찾기
            high -= 1
            condition = high >= left and arr[high] > pivot
            if not condition:
                break

        if low < high: #찾은 두 데이터를 교환해준다
            arr[low], arr[high] = arr[high], arr[low]

        if low > high:# 부분 정렬 완료
            break

    arr[left], arr[high] = arr[high], arr[left]
    return high

def quick_sort(arr, left, right):
    if left < right:
        pivot = partition(arr, left, right)#분분 정렬 후 pivot의 위치 반환
        quick_sort(arr, left, pivot-1) #피벗의 왼쪽 데이터에 대해 분할 실시
        quick_sort(arr, pivot+1, right) #피벗의 오른쪽 데이터 대해 분할 실시

References

• 위키백과 - 퀵정렬
• Do it! 자료구조와 함께 배우는 알고리즘 입문(한빛미디어)
• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html