Quick Sort

• 개념 : 리스트를 피벗을 기준으로 분할하고 분할한 리스트를 재귀로 정렬한 후 결합하는 알고리즘.
• 특징
  • 비교 정렬(다른원소와의 비교만으로 정렬 수행)
  • 분할 정복 알고리즘의 하나
  • 매우 빠른 수행 속도
  • 분할, 정복, 결합
  • 리스트를 비균등하게 분할
• 시간복잡도
  • $O(nlog_2n)$ : n * 순환호출의 깊이 / 횟수 : $O(log_2n)$ 균등하게 분할
  • $O(n^2)$ : 리스트가 불균형하게 나누어지는 경우(특히, 이미 정렬된 리스트)
• 공간복잡도 : $O(log n)$
• 장점
  • 빠른 속도
  • 추가 메모리 필요 x
• 단점
  • 정렬된 리스트라면 수행시간 더 걸림

💡 퀵정렬 피벗값 선정 방법
리스트 맨 앞의 값 or 중앙값 or 랜덤값 하나 or 랜덤값 3개 중 중앙값

arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

# Solution 1
def quick(arr, start, end):
    if start >= end:
        return
    pivot, left, right = start, start+1, end
    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]
    quick(arr, start, right-1)
    quick(arr, right+1, end)
    

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

# Solution 2
def quick(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    tail = arr[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick(left_side) + [pivot] + quick(right_side)
    

# quick(arr, 0, len(arr)-1)
print(quick(arr))