정렬 메모

import random
 
def quick(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    arr = arr[1:len(arr)]
    left_arr = []
    right_arr = []
    for x in arr:
        if x < pivot:
            left_arr.append(x)
        else:
            right_arr.append(x)

    left_arr = quick(left_arr)
    right_arr = quick(right_arr)
    
    left_arr.append(pivot)
    return left_arr + right_arr

_arr =random.sample(range(100), 100)
print(quick(_arr))

merge 방식에 quick의 pivot을 도입하였다.

구현을 하면서 제일 헷갈리면서도 issue가 되는 부분이 swap이다.

서로 다른 index 간 데이터가 제대로 잘 변경되는지 확인하는 것이 여간 귀찮지가 않다.

구현할 때마다 항상 찝찝한 기분이 들기도 한다.

위 코드는 swap이 없기 때문에 메모리 이용이 많다.

알고리즘 복잡도는 $nlog_2n$이다.