파이썬, 빠른 정렬(퀵 소트, Quick Sort)

호어 선생님이 만드신 빠른 정렬~!

분할 정복 알고리듬을 이용합니다. 
(머지 소트도 분할 정복이죠.)

불안정 정렬입니다. 
([A1, A2]를 'A를 기준'으로 '숫자를 무시'하고 정렬했을 때 
A1, A2의 순서가 바뀔 수 있습니다.)

[A, B, A, C, A]를 정렬하면 [A, A, A, B, C]가 되는데.. 
A, A, A 간 순서가 어떻게 되든 무슨 상관이냐 라고 생각할 수 있는데..

[A1, B2, A2, C1, A3]의 경우
두 번째 숫자를 기준으로 정렬한 뒤, 
[A1, C1, B2, A2, A3]를
첫 번째 문자를 기준으로 한 번 더 정렬해서,
[A1, A2, A3, B2, C1]를
만들어야 할 경우도 있습니다. 

(스프레드 시트 작업에서 많이 씁니다. )

불안정 정렬로는 이런 작업이 어렵습니다. ~!

 

이 분이 영국 남자 호어 선생님

 

설명을 위해 직접 그림을 그리려다가...
그냥 구글링 했습니다. 

그림을 잘 그려놓으셨습니다. 
한 번에 이해가... ~!

좋아요 클릭해드렸습니다. 

https://coderkoo.tistory.com/7 

퀵소트(quick sort) 알고리즘

 

자료를 수집하러 위키백과에 들어갔다가
퀵 소트를 구현한 파이썬 코드를 봤습니다.
파이썬스럽고 '재미있는' 코드라는 생각이 들었습니다.

그런데 위키백과의 의사(pseudo) 코드를 보니 이 코드랑 똑같네요!
제 가방끈이 짧아서 원 알고리듬도 못 알아본 것이었... ㅠ,.ㅠ

# https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#%ED%8C%8C%EC%9D%B4%EC%8D%AC

def quick_sort1(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    less, more, equal = [], [], []
    for each in array:
        if each < pivot:
            less.append(each)
        elif each > pivot:
            more.append(each)
        else:
            equal.append(each)
    return quick_sort1(less) + equal + quick_sort1(more)


print(quick_sort1([51, 20, 72, 63, 32, 75, 2, 88, 16, 29]))

"""
[2, 16, 20, 29, 32, 51, 63, 72, 75, 88]
"""

메모리를 절약하도록 수정해 보았습니다.
(파이썬 GC가 알아서 처리하려나...)

def quick_sort2(array):
    length = len(array)
    if length <= 1:
        return array
    pivot = array[length // 2]
    less, more, equal = [], [], []
    for each in array:
        if each < pivot:
            less.append(each)
        elif each > pivot:
            more.append(each)
        else:
            equal.append(each)
    del array  #
    return quick_sort2(less) + equal + quick_sort2(more)

 

리스트를 만들고, append 하는 데도 비용이 발생합니다. 
리스트를 하나만 유지하고, 요소의 순서를 바꿔줍니다. 
재귀 함수에는 배열의 '참조'와
배열에서 처리해야 할 부분의 시작과 끝의 '위치'만
넘겨줍니다. 

이렇게 코딩하면 더 빠를 줄 알았지만...

파이썬에서 배열은 기본적으로 참조(by reference)입니다.   

pivot의 위치를 시작, 끝, 랜덤으로 지정하는 경우도 많습니다.

# https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#%ED%8C%8C%EC%9D%B4%EC%8D%AC

def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and pivot <= arr[right]:
            right -= 1
        if right < left:
            done = True
        else:
            arr[left], arr[right] = arr[right], arr[left]
    arr[start], arr[right] = arr[right], arr[start]
    return right


def quick_sort3(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quick_sort3(arr, start, pivot - 1)
        quick_sort3(arr, pivot + 1, end)
    return arr


print(quick_sort3([51, 20, 72, 63, 32, 75, 2, 88, 16, 29], 0, 9))

 

조금 더 파이썬스럽게 중첩함수(함수 내 함수)를 이용한다면... 

def quick_sort3(arr):
    def partition(start, end):
        pivot = arr[start]
        left = start + 1
        right = end
        done = False
        while not done:
            while left <= right and arr[left] <= pivot:
                left += 1
            while left <= right and pivot <= arr[right]:
                right -= 1
            if right < left:
                done = True
            else:
                arr[left], arr[right] = arr[right], arr[left]
        arr[start], arr[right] = arr[right], arr[start]
        return right

    def quick_sort(start, end):
        if start < end:
            pivot = partition(start, end)
            quick_sort(start, pivot - 1)
            quick_sort(pivot + 1, end)

    quick_sort(0, len(arr) - 1)
    return arr

 

2가지 경우만 이해해 봅시다.

 p
[6, 3, 1, (L)9, (R)2]

 

Left는 pivot 다음 요소부터 'pivot보다 작으면 진행' 
pivot보다 큰 요소(9)를 발견하면 3에 멈춥니다.

Right는 마지막 요소부터 'pivot보다 크면 진행'
pivot보다 작은 요소(2)를 발견하면 4에 멈춥니다. 

 

멈추면 피봇 보다 큰 것 작은 것이 하나씩 나왔으니까 
둘(right와 left)을 교환합니다.

 p
[6, 3, 1, 2, 9]

 

left와 right가 만날 때까지 위 과정을 반복합니다.
(위 예시는 반복할 것이 없습니다.)

 

마지막으로 start(=0)와 right(=3)을 교환하고 pivot = right.  

          p
[2, 3, 1, 6, 9]

퀵 소트의 조건에 맞게 정리되었습니다. 

 

만약에 한 방향으로만 진행된다면... 

 p
[6, 3, 1, 4, 5]

left=4이고 right=4가 됩니다.  

 

마지막 과정인 right와 pivot을 교환하는 과정을 거치면 다음과 같죠...

             p
[5, 3, 1, 4, 6]

마찬가지로 퀵 소트의 조건에 맞게 정리되었습니다. 

 

시간 테스트를 해 보았습니다. 

from random import randint
import time


def check_time(f, *args):
    start_time = time.time()
    f(*args)
    end_time = time.time()
    print(f"{f.__name__}: {end_time - start_time}")


nums = [randint(0, 100000) for _ in range(100000)]

check_time(quick_sort1, nums[:])
check_time(quick_sort2, nums[:])
check_time(quick_sort3, nums[:])

파이썬은 함수를 인자(매개변수 f)로 사용할 수 있습니다. 
함수의 이름을 알기 위해 f.__name__을 사용했습니다. 
quick_sort4 때문에 가변인자를 받기 위해 *args를 사용했습니다. 
파이썬의 리스트는 참조입니다.
리스트를 복사하기 위해 nums[:]를 사용했습니다. 
nums.copy() 도 됩니다. 

실행할 때 마다 약간씩 달라집니다만...
경향성은 파악할 수 있습니다. 

quick_sort1: 0.2385568618774414
quick_sort2: 0.240553617477417
quick_sort3: 0.29744744300842285

제 예상과 달리, 파이썬에서는 세 번째 코드가 느렸습니다. 1, 2번 코드는 비슷했습니다. 엎치락 뒷치락...