퀵 소트

퀵 정렬

개념

• 퀵 정렬은 분할 정복 방법을 통해 배열을 정렬한다.
  • 분할 정복(divide and conquer): 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 또한 Merge Sort 와 달리 Quick Sort 는배열을 비균등하게 분할한다.

특징

• 파이썬의 list.sort() 함수나 자바의 Arrays.sort() 처럼 프로그래밍 언어 차원에서 지원되는 내장정렬함수는 대부분 퀵 정렬을 기본으로 한다.
• 일반적으로 원소의 개수가 적어질 수록 나쁜 중간값이 선택될 확률이 높아지기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해 쓰는 경우가 많다.
• 병합정렬과 퀵정렬은 분할 정복과 재귀 알고리즘을 사용하는 분할 정복과 재귀 알고리즘을 사용하는 측면에서는 유사해보이지만, 내부적으로 정렬을 하는 방식에는 큰 차이가 있다.
• 병합 정렬은 항상 정 중앙을 기준으로 단순 분할 후, 병합 시점에서 값의 비교 연산이 발생하는 반면, 퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에, 이후에 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라, 아예 병합 안하는 경우가 있다.

복잡도

• 퀵 정렬의 성능은 어떻게 pivot 을 선택하냐에 따라 달라진다. 이상적인 경우, pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합정렬과 마찬가지로 O(N log N ) 의 시간 복잡도를 가지게 됩니다.
• 하지만 pivot 값을 기준으로 분할했을 때, 값들이 한 편으로 치우치게 되면, 퀵 정렬은 성능이 저하되게 되고, 최악의 경우 한편으로만 모든 값이 몰려 O(n**2) 의 시간복잡도를 보이게 됩니다.
• 따라서, 상용코드에서는 중앙값에 가까운 pivot 값이 선택될 수 있는 섬세한 전략이 요구되며, 배열의 첫 값과 중앙값 그리고 마지막 값 중에 크기가 중간이 값을 사용하는 방법이 많이 사용됩니다.
• 퀵 정렬은 공간복잡도가 구현 방법에 따라 달라질 수 있는데, 입력 배열이 차지하는 메모리만을 사용하는 in-place sorting 방식으로 구현할 경우 O(1) 의 공간복잡도를 가진 코드의 구현이 가능합니다.

구현 ( not in - place )

def quick_sort(arr):
    if len(arr)<2:
        return arr
    pivot = arr[len(arr)//2]
    leser_arr, equal_arr, greater_arr =[],[],[]
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num> pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
        else:
            equal_arr.append(num)
     return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

위의 구현은 간결하고 이해하기 쉽지만, 매번 재귀 호출될 때마다 새로운 리스트를 생성해 리턴하기 때문에 메모리 사용 측면에서 비효율적입니다.

구현(in-place)

def quick_Sort(arr):
    def sort(low, high):
        if high <=low:
            return
        mid = partition(low, high)
        sort(low, mid -1)
        sort(mid,high)
    def partition(low, high):
        pivot = arr[(low+ high)//2]
        while low <= high:
            while arr[low] > pivot:
                low+=1
            while arr[high] > pivot:
                high-=1
            if low<=high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low +1, high-1
        return low
    retyrn sort(0, len(arr)-1)

참고 문헌

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