Ch 03. 分割征服アルゴリズム(1)

MergeSort(A, p, q): #배열 A, 첫 인덱스 p, 끝 인덱스 q
    if p < q: 		#배열 내 원소가 2개 이상일 때
        k = (p + q) // 2	#절반 위치 인덱스(몫만 취함)
        MergeSort(A, p, k)     #앞부분 순환 호출
        MergeSort(A, k + 1, q) # 뒷부분 순환 호출
        Merge(A, p, q)		#부분 배열 합병 정렬  

def quick_sort(arr, start, end):
    if start >= end: return 
    pivot = arr[start] # 피벗은 첫번째 원소
    l, r = start + 1, end

    while l <= r:
        while l <= end and arr[l] <= arr[pivot]:
            l += 1
        while r > start and arr[r] >= arr[pivot]:
            r -= 1
        if l > r: 
            arr[r], arr[pivot] = arr[pivot], arr[r]
        else: 
            arr[r], arr[l] = arr[l], arr[r]
    quick_sort(arr, start, r - 1)
    quick_sort(arr, r + 1, end)

A = [5, 3, 8, 4, 9, 1, 6, 2, 7, 10]
print(quick_sort(A, 0, len(A)))