[알고리즘] 퀵 소트 공부해보기

분할정복 알고리즘인 퀵 소트에 대해 공부해보았다.

https://www.daleseo.com/sort-quick/

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)

여기에서 상상 이상으로 정리가 잘 되어있다.

 

기본이 있고, 최적화하는 방법이 있는데 나는 일단 기본부터 외워보기로 했다.

의외로 구현이 간단해서 놀라웠다. 금방 외울 수 있었다.

def qsort(arr):
    if len(arr) <= 1:
        return arr
    l,e,r = [],[],[]
    mid = arr[len(arr) // 2]
    for i in range(len(arr)):
        if mid > arr[i]:
            l.append(arr[i])
        elif mid < arr[i]:
            r.append(arr[i])
        else:
            e.append(arr[i])

    return qsort(l) + e + qsort(r)


print(qsort([4,1,2,6,9,7]))