Quick Sort(퀵 정렬)

퀵정렬은 분할과 정복의 알고리즘이다

1. 특정값(pivot)을 기준으로 작은값과 큰값을 나누면서 정렬을 하는 방법

2. 시간복잡도 : O(nlogn)
3. 특정값을 한쪽으로 치우쳐져 잡거나 잘못 잡으면 O(n^2)에 수렴된다

Credit.  https://medium.com/karuna-sehgal/a-quick-explanation-of-quick-sort-7d8e2563629b

 

Credit. https://www.pillowfort.social/dibit/tagged/these%20are%20always%20so%20pretty

 

## 배열 swap 함수
def swap(arr, a,b):
    temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp


## 퀵 정렬
def Quicksort(arr, start, end):
    if start >= end: ##더 이상 나눌게 없으면 리턴으로 마무리
        return     

    pivot = start ##pivot 변수를 가장 좌측으로 시작했음 기준이 되는 값
    left = start + 1 ##이미지와 달리 저는 pivot값을 좌측 끝으로 시작했습니다.
    right = end

    while left <= right : ##좌측 시작값이 우측보다 커지면 멈춰야됨
        while left <= end and arr[left] <= arr[pivot]: ## pivot 값보다 작으면 패스 크면 정지
            left += 1
        while right > start and arr[right] > arr[pivot]: ## pivot 값보다 크면 패스 작으면 정지
            right -= 1
        if left > right: ## 만일 left 위차와 right 위치가 교차되면 마지막 작은 값을 pivot값과 위치변환
            swap(arr, pivot, right)
        else: ##교차되지 않은 경우 left가 찾은 큰값과 right가 찾은 작은값 swap
            swap(arr, left, right)

    Quicksort(arr, start, right-1) ##퀵정렬 답게 디바이드된 좌측쪽만 재귀 반복
    Quicksort(arr, right+1, end) ##퀵정렬 답게 디바이드된 우측쪽만 재귀 반복



####main 함수####
arr = [7,9,8,3,1,4,6,2,5]

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