Quick Sort

yijin3018·2021년 11월 11일
0
  • 개념 : 리스트를 피벗을 기준으로 분할하고 분할한 리스트를 재귀로 정렬한 후 결합하는 알고리즘.
  • 특징
    • 비교 정렬(다른원소와의 비교만으로 정렬 수행)
    • 분할 정복 알고리즘의 하나
    • 매우 빠른 수행 속도
    • 분할, 정복, 결합
    • 리스트를 비균등하게 분할
  • 시간복잡도
    • O(nlog2n)O(nlog_2n) : n * 순환호출의 깊이 / 횟수 : O(log2n)O(log_2n) 균등하게 분할
    • O(n2)O(n^2) : 리스트가 불균형하게 나누어지는 경우(특히, 이미 정렬된 리스트)
  • 공간복잡도 : O(logn)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))
profile
💻 For Computer Science..

0개의 댓글