[알고리즘] 파이썬으로 퀵정렬(Quick Sort) 구현하기

이전까지 기록했던 알고리즘 (선택정렬, 버블정렬, 삽입정렬)들은 시간 복잡도가 O(N**2)로 데이터의 개수가 증가하게 되면, 처리속도가 매우 느려지는 알고리즘들이었다. 하지만, 이번에 구현해보려는 퀵정렬의 경우, 평균적인 복잡도가 O(N*logN)으로 상대적으로 빠른 알고리즘이다. 

 

퀵정렬의 정의는 다음과 같다. 

" 기준값(pivot)을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 분리하며 정렬하는 방법이다 "

정의에서 볼 수 있는 중요 포인트는 1) 기준값이 존재한다는 점, 2) 기준값을 기준으로 분리를 하는 분할정복 알고리즘이라는 것이다. 알고리즘을 이해하고, 상식선에서 같이 알고 넘어가자. 

 

# 퀵정렬: 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤, 배열을 반으로 나눠 정렬
def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1
    right = end
    done = False
     # left와 right가 엇갈릴 때까지 반복
    while not done:
        # pivot 보다 작은 값을 만날 때까지 반복
        while left <= right and arr[left] <= pivot:
            left += 1
        # pivot 보다 큰 값을 만날 때까지 반복
        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(arr, start, end):
    if start < end:
    	print(arr)
        pivot = partition(arr, start, end)
        quick_sort(arr, start, pivot - 1) # pivot 보다 작은 왼쪽에 적용
        quick_sort(arr, pivot + 1, end) # pivot 보다 큰 오른쪽에 적용
    return arr

quick_sort(array, 0, len(array)-1)

원래 알고리즘에서 코드를 작성할 때는 '안경잡이 개발자' 블로그 및 유튜브를 참고하는데, 이번에는 위키피디아의 소스코드를 참고하였다. 코드 자체는 거의 비슷하고, 구현하는 결과도 거의 비슷했는데, 맨마지막 정렬이 안이뤄져 그에 대한 이유를 아직은 모르겠어서 위키피디아의 내용을 참고했다. 

 

(원래는 한 함수 내에 모든 것을 끝내려고 했는데, 위키처럼 나눠서 하는 게 나중에 코드에 대한 유지보수의 관점에서 더 쉬울 것이란 생각이다)

 

순서:

1. pivot 값을 설정한다

2. pivot을 기준으로 보다 큰 값을 만날 때까지(right), 그리고 작은 값을 만날 때까지(left) 비교한다

3. 위에서 찾은 right이 left보다 크면 (값이 엇갈리면) 교체한다

4. pivot 왼쪽과 오른쪽에 위 순서를 반복한다

 

 

동작하는 것을 보면 아래 사진과 같이 출력되는 것을 확인할 수 있다. (중복되서 출력되는데, 이건 quick_sort 함수 초반에 print를 하는데, 아래에서는 그 함수를 두번이나 적용하기 때문이다)

 

참고자료:

- 안경잡이 개발자, "5. 퀵 정렬(Quick Sort)", https://m.blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

- Wikipedia, "Quick Sort(퀵 정렬)", https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전