퀵 정렬

퀵정렬은 가장 널리 사용되는 정렬 알고리즘이다😎

- 퀵정렬의 메인 아이디어
피벗을 설정하고 그 피벗을 기준으로 리스트를 좌우로 나누어 재귀적으로 정렬을 수행하여 해결

퀵정렬의 수행 과정

1. 피벗을 설정한다
2. 그 기준보다 큰 수와 작은 수를 교환한다
3. 피벗으로 리스트를 반으로 나누어 재귀적으로 수행한다.

시간 복잡도

• 평균 : $O(NlgN)$
• 최악 : $O(N^2)$
  최악의 경우는 리스트가 이미 정렬되어 있는 경우 분할이 한쪽으로 치우쳐서 결국 $O(N^2)$이 된다.

코드

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

def quick_sort(array, start, end):
    # 크기가 1이면 종료
    if start >= end:
        return
    pivot = start
    left = start+1
    right = end
    # 엇갈릴때까지 수행(더이상 정렬할 필요가 없을때까지)
    while left <= right:
        # 왼쪽에서부터 pivot 보다 큰 값 탐색
        while left <= end and array[pivot] >= array[left]:
            left += 1
        # 오른쪽에서부터 pivot 보다 작은 값 탐색
        while right > start and array[pivot] <= array[right]:
            right -= 1
        # 엇갈렸다면 pivot과 right 교체
        if left > right:
            array[pivot], array[right] = array[right], array[pivot]
        # 그게 아니라면 left와 right 교체
        else:
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

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