퀵 정렬

파이썬의 경우 가장 빠른 퀵솔트로 sort()함수가 구현이 되어있다. 

 

퀵 솔트란?

기준 데이터를 설정하고 그 기준 보다 작은 데이터들을 왼쪽으로 큰 데이터들은 오른쪽으로 위치를 바꾸어 주며, 바뀐 데이터들 이와 같은 방법으로 재귀적으로 실행되며 정렬되는 방식.

 

 평균적인 시간 복잡도는 O(nlogn)이고 최악의 경우, O(n**2)이 된다. 정렬 알고리즘 중 가장 빠른 시간을 자랑하지만, 기준 데이터에 따라 최악의 시간 복잡도를 가질 수 있다. 따라서, 적절한 pivot(기준)을 정해주는 것이 중요하겠다. python 또한, 내부적으로 항상 nlogn으로 pivot을 설정하여 작동하게 끔 구현이 되어있다.  

def quick_sort(array: list) -> list:
    if len(array) <= 1:
        return array

    pivot = array[0] # pivot을 원소 첫번째 값으로 설정
    tail = array[1:] # pivot을 제한 나머지 원소들

    left_side = [x for x in tail if x <= pivot] # 기준 보다 작은 부분
    right_side = [x for x in tail if x > pivot] # 기준 보다 큰 부분

    # 재귀를 통해 왼쪽 부분과 오른쪽 부분을 계속해서 리스트의 길이가 1일 때까지 정렬하여 합친 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)


print(quick_sort([5,7,8,9,0,3,1,2,6,4]))
# result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

병합 정렬과 비교하여 가장 많이 사용이 된다. 병합 정렬의 경우, 최악의 시간 복잡도의 경우에도 O(nlogn)으로 평균적으로 빠르다고 볼 수 있지만, 퀵솔트는 기준값만 잘 설정해준다면 가장 빠른 시간으로 구현이 가능하다. 그리고 사용되는 공간의 경우에도 병합정렬은 모든 원소를 1개 단위로 쪼개어 합치기 때문에 n만큼 사용되지만, 퀵 정렬은 리스트를 두 구간으로 쪼개어 재귀 실행하기에 logn 만큼 공간이 활용된다는 이점도 있다.

 

결론, 퀵솔트는 pivot 값이 잘 설정된다면 평균적인 정렬속도가 매우 빠르다는 점과 재귀적으로 리스트가 2개씩 나누어지기에 logn에 비례하는 공간 복잡도로 병합정렬에 비해 상대적으로 적은 공간을 활용한다고 볼 수 있다.