[python] 퀵 정렬 구현

킹빈나님의 영상을 보고 퀵 정렬 구현을 따라해봤다.

영상 링크

이코테 2021 강의 몰아보기 4. 정렬 알고리즘

퀵 정렬 설명
가장 앞에 있는 원소를 pivot으로 앞에서부터 pivot보다 큰 놈을 찾고, 뒤에서부터 pivot보다 작은 놈을 찾는다. 발견하면 서로 swap
그렇게 가다가 더이상 찾을게 없으면(앞에서 찾는 지점과 뒤에서 찾는 지점이 서로 부딪히면)
피벗을 앞에서 찾는 지점과 뒤에서 찾는 지점 중 작은데이터와 swap

두개로 찢어서 다시 위의 알고리즘 반복

이렇게 재귀적으로 가다보면 구현 완료
시간 복잡도는 높이가 logN, 길이가 N이므로 O(NlogN)이고, 최악의 경우 O(N^2)가 된다.

코드

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end:    #원소가 1개인 경우 종료
        return
    pivot = start   #피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right):   #엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:   #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 오니쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)


print(array)    #정렬 안됨 [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
quick_sort(array, 0, len(array) - 1)
print(array)    #정렬 됨 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]