[Sort] 퀵 정렬 - Quick Sort

기준(Pivot)을 두고 기준 왼쪽에는 작은 수들을, 기준 오른쪽에는 큰 수들을 놓는다. 이러한 과정을 기준을 제외하고 왼쪽 부분(기준보다 작은 아이들) / 오른쪽 부분(기준보다 큰 아이들)에 똑같이 적용하여 반복한다

Pivot을 기준으로 작/큰 분류 - Tree 처럼 반복 / swap 시 Index 범위 조심!

 

주의

오른쪽부터 탐색하는 포인터(코드에서는 right)가 arr의 범위를 넘어가지 않는 포인터이다. pivot을 항상 맨 첫번째 Idx로 정하기 때문이다. 모두 정렬이 되어있는 경우 왼쪽부터 탐색하는 포인터(코드에서는 left)는 arr의 범위를 넘어간다. 

따라서 left와 right가 교차했을 시에, right 자리를 pivot과 swap해주어야 기준이 중간으로 범위 벗어난 문제 없이 이동할 수 있다.

 

시간복잡도

기준을 중심으로 두 부분씩 분할되어 정렬을 진행하기 때문에 트리 형식으로 볼 수 있다.

예를 들어 8개의 Data라면 3의 Depth가 생성된다. 각 Depth에서 N번의 비교가 발생할 수 있으니 O(NlogN)이다

 

import sys
input = sys.stdin.readline

arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19]

def quickSort(start, end, arr):
    if start>=end :
        return
    pivot = start
    left = start+1
    right = end
    while True:
        while arr[left] <= arr[pivot] and left <= end: #범위 조심
            left+=1
        while arr[right] >= arr[pivot] and right > pivot: #범위 조심
            right-=1
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right] #기준 Swap Right이랑 할 것!
            quickSort(0, right-1, arr)
            quickSort(right+1, end, arr)
            break
        else:
            arr[left], arr[right] = arr[right], arr[left]


quickSort(0, len(arr)-1, arr)
print(arr)