[Python] Quick_sort 구현 - non-iterative, sorted before recursio

import time
from typing import MutableSequence

def qsort(a: MutableSequence, left : int, right : int) -> None:
    pl = left
    pr = right
    pivot = a[(left+right) // 2]

    while pl <= pr: 
        while a[pl] < pivot: 
            pl += 1
        while a[pr] > pivot: 
            pr -= 1
        if pl <= pr: 
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    if left < pr: 
        qsort(a, left, pr) 
    if pl < right: 
        qsort(a, pl, right)
        
def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬 시작"""
    print(quick_sort.__doc__)
    qsort(a, 0, len(a)-1)

if __name__ == "__main__":
    start = time.time()

    data = [3,1,-5,7,-4,2,6,200,9,-2,4,3,0,-2] + [100] * 100000
    quick_sort(data)
    sum = 0
    for _, val in zip(range(20), data):
        sum += val * val
        if sum > 50:
            print('Sum = ', sum)
    
    print(f'1000을 넘지 않은 최대 sum : {sum}')
    print(f'경과 시간 : {int((time.time()-start)*1000)}ms')

주어진 코드는 이지스 퍼블리싱에서 출판한 “자료구조와 함께 배우는 알고리즘 입문 파이썬 편”의 p261, “퀵 정렬 알고리즘 구현하기”에서 인용하였습니다.

 

quick sort의 특징은 pivot이 존재하고, 이 pivot을 기준으로 정렬하는 것입니다. 1번 코드와 2번 코드의 경우 이 pivot을 첫 번째 원소로 지정하였지만, 3번 코드는 가운데 원소로 하였습니다.

 

방식은 다음과 같습니다.

 

1. pl을 주어진 리스트의 0번째 index로 지정하고, pr을 주어진 리스트의 마지막 index로 지정합니다.

 

2. a[pl]이 pivot보다 값이 클 때까지 pl의 값을 증가하고, a[pr]이 pivot보다 값이 작을 때까지 pr의 값을 감소합니다.

 

3. 두 while이 끝났다는 것은 a[pl]이 pivot보다 큰 값을 가지고 있고, a[pr]이 pivot보다 작은 값을 가지고 있음을 의미합니다. 오름차순으로 정렬하기 위해서 두 값의 위치는 반대가 되어야 합니다. 그러므로 두 값의 위치를 변경하고, 2번부터 과정을 다시 진행합니다. 단, 2~3의 과정은 pl <= pr 인 경우에서만 반복합니다.

 

예를 들어, [5,9,4,2,3,7,6,1]의 경우, [1, 2, 4, 9, 3, 7, 6, 5]으로 리스트가 변경되고, pl은 2, pr은 1이 된다. 이후 인덱스 기준 0~1까지, 1~7까지 quick sort를 진행한다. 만약 pl과 pr의 차이가 1 이상이라면 그 사이에 있는 값들은 옳게 정렬된 것 이므로 정렬할 필요가 없다.

 

4. 이 과정을 무한히 반복한다. recursive 함수를 구현하기 위해선 종료 조건을 반드시 명시해야만 한다. 1,2번 코드에서도 이를 위하여 주어진 리스트가 공집합일 때 아무런 행동을 하지 않고 그대로 return 한다. 3번 코드의 경우, 피벗보다 왼쪽에서 더 이상 정렬할 필요가 없는 경우 left와 pr의 값이 같게 된다. 마찬가지로 피벗보다 오른쪽에서 더 이상 정렬할 필요가 없는 경우, pl과 right의 값이 같게 된다. 이 경우 quick sort를 진행하지 않게 됨으로써 종료 조건을 만족한다.