[Algorithm] 퀵 정렬(quick sort)

퀵 정렬

- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 동작

- 호어 분할 방식
    -> 리스트에서 첫번째 데이터를 pivot(기준)으로 정한다.
    -> 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 
    -> 큰 데이터와 작은 데이터의 위치를 서로 교환

- 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복

- 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해진다

- 퀵 정렬의 시간복잡도 : O(NlogN) 
    -> 삽입 정렬과 달리 데이터가 거의 정렬되어 있는 최악의 경우 시간복잡도가 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:
        # 피벗보다 큰 데이터 찾을 때까지 반복
        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,end-1)

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