개발하는데 다 이유가 있겠지

퀵 정렬(Quick Sort)

가장 빠른 정렬 알고리즘으로 알려져있음

피벗(pivot)을 기준으로 좌측에는 피벗보다 작은 값, 우측에는 큰 값을 정렬

def qsort(arr, start, end):
    # 배열과 좌우 끝 인덱스
    pl = start
    pr = end
    # 피봇값 지정
    pivot = arr[(pl+pr)//2]

    # 우측 인덱스가 좌측 인덱스가 크거나 같을동안 진행
    while pl <= pr:
        # 피봇보다 작으면 진행, 크면 탈출
        while arr[pl] < pivot:
            pl += 1
        # 피봇보다 크면 진행, 작으면 탈출
        while arr[pr] > pivot:
            pr -= 1
        # 좌우 인덱스가 교차하지 않을때 swap
        if pl <= pr:
            arr[pl], arr[pr] = arr[pr], arr[pl]
            # 교차하고 나서도 인덱스 증감
            pl += 1
            pr -= 1
        # pr이 좌측의 끝값
        if start < pr:
            qsort(arr, start, pr)
        # pl이 우측의 시작값
        if end > pl:
            qsort(arr, pl, end)


array = [5, 2, 6, 7, 4, 3, 8, 1, 9, 0]
qsort(array, 0, 9)
print(array)	# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

• 피벗(pivot)의 위치는 중앙값을 피벗으로 하는게 이상적임(배열의 원소가 3개 이상일 경우)
• 시간복잡도 O(n log n) / 최악 O(n^2) -> 매번 1개의 원소와 나머지 원소로 나누어지는 경우