파이썬으로 구현하는 퀵 정렬(Qucik Sort)

Concept

병합 정렬(Merge Sort)과 마찬가지로, 퀵 정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 $O(nlogn)$이다

하나의 리스트에서 피봇(pivot)이라고 불리는 임의의 기준값을 사용하여 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과 큰값의 그룹으로 나눈다. 이 때 두 그룹의  각 요소들은 정렬된 상태는 아니지만, pivot은  정렬된 위치로  들어가게되며 이를 재귀호출을 통해 정렬하게 된다. 전체적인 동작 과정은 다음과 같다

퀵 정렬; 오름차순

 

구현 코드

(아래 코드는 pivot을 arr의 첫번째 요소로 잡은 코드입니다; pivot = arr[0])

1) 정렬되지 않은 데이터 -> 리스트로 입력 받기

>>>3 2 4 6 9 1 8 7 5
arr = [int(x) for x in input().split()]

2) quick sort

partition 함수는  pivot의 전체 리스트에서 정렬된 위치를 반환한다

def quick_sort(arr, i, j):
    if i < j:
    	pivot = partition(arr, i, j) # pivot의 정렬된 위치를 반환받음 
        quick_sort(arr, i, pivot-1) # pivot을 기준으로 작은 그룹
        quick_sort(arr, pivot+1, j) # pivot을 기준으로 큰 그룹

3) partition

pivot을 전체 리스트에서 정렬된 위치로 이동시켜주며, pivot을 기준으로 왼쪽은 작은 값을, 오른쪽은 큰 값을 두게 된다

def partition(arr, s, e):

    # pivot을 arr의 첫번째 원소값으로 초기화
    pivot_idx = s
    pivot = arr[pivot_idx]
    
    while s < e:
        # arr[s]가 pivot보다 크면 스탑
    	while s < len(arr) and arr[s] <= pivot: 
            s += 1
            
        # arr[e]가 pivot보다 작으면 스탑
        while arr[e] > pivot: 
            e -= 1  
            
        # s,e위치가 스왑되지 않았다면 arr[s],arr[e]를 스왑
        if s < e: 
            arr[s], arr[e] = arr[e], arr[s]
        
    # s > e 상태로 현재 e의 위치는 pivot의 정렬된 위치임
    # 따라서 arr[e], arr[pivot_idx]를 스왑
    arr[e], arr[pivot_idx] = arr[pivot_idx], arr[e]
    
    # pivot의 정렬된 위치 반환
    return e

3) 정렬결과 확인

quick_sort(arr, 0, len(arr)-1)
print(arr)
>>>1 2 3 4 5 6 7 8 9