[자료구조] 퀵 정렬(Quick Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

퀵 정렬(Quick Sort)

개념

• 퀵 정렬은 기준값(Pivot)을 중심으로 Pivot보다 작으면 왼쪽, 크면 오른쪽으로 분할해 줍니다. 그런 다음 분할된 하위 리스트들을 다시 재귀적으로 pivot을 뽑고 pivot보다 작으면 왼쪽, 크면 오른쪽으로 분할해 줍니다. 이런 식으로 쭉 진행하게 되면 정렬된 리스트를 얻을 수 있습니다.
  • 
• 퀵 정렬은 병합 정렬(merge sort)보다 잘 구현되면 2~3배 더 빠를 수 있습니다. 이러한 이유로 퀵 정렬이라는 이름이 붙었습니다.
  • 하지만 최악의 경우 O(N^2)의 시간이 걸릴 수 있습니다. 최선의 경우는 O(NlogN)입니다. 이는 이제 피봇 기준으로 왼쪽 오른쪽이 정확히 2등분 되면 최선의 경우가 되고, 피봇 기준 한쪽으로 치우치게 되면 계속해서 1, n-1개로 나누어지게 됩니다. 이럴 경우에는 계속해서 탐색을 진행해야 하므로 O(N^2)이 되는 것입니다.
• 그렇다면 왜 퀵정렬이 제일 빠르다고 하는 것일까요?
  • 이는 이제 다른 알고리즘에 비해 캐시 효율성이 좋기 때문입니다. 캐시 효율성이 좋은 주된 이유는 지역성(locality) 때문입니다. 퀵 정렬은 분할 과정에서 연속적인 데이터 블록을 다루기 때문에 시스템의 캐시 메모리 활용도가 높아집니다. 캐시 히트 확률이 높아서 메모리 접근시간이 단축됩니다. 다른 알고리즘의 경우, 한번 정렬 시에 여러 부분의 배열을 접근해야 하기 때문에 캐시 미스가 더 자주 발생합니다. 
  • 비교
    • 병합 정렬
      • 
    • 퀵 정렬
      • 
    • 위의 정렬 과정을 살펴보게 되면 퀵 정렬의 경우 pivot을 기준으로 pivot보다 더 작은 값은 왼쪽으로 보내고, pivot보다 더 큰 값은 오른쪽으로 보내게 됩니다. 그 후에 이제 다시 재귀적으로 그 왼쪽 부분에 대해서 탐색을 진행하게됩니다. 결론적으로 더 작은 부분 안에서 데이터를 정렬하기 때문에 캐시 hit가 더 자주 발생해서 직접 물리적 데이터에 접근하지 않고도 빠르게 정렬이 가능해집니다.
    • 하지만 이제 병합 정렬의 경우, 작은 단위로 나누고 다시 합치는 과정에서 나눠진 두 배열의 데이터를 이용해야합니다. 결국 이럴 경우 캐시 안의 용량의 한계로 캐시 안의 데이터는 계속해서 변경이 이루어질 것이고, 결국에는 캐시 miss가 계속해서 발생하게 되어 직접 물리적 데이터에 계속해서 접근해 시간이 더 많이 소요될 것입니다. (힙 정렬의 경우도 마찬가지입니다. 힙 자료 구조를 계속 유지하고 있어야 하므로 이 또한 캐시 미스가 많이 발생합니다.)
  • 또한 이제 퀵 정렬의 경우 in-place방식으로 정렬됩니다. 병합 정렬의 경우 새로운 배열을 생성한 뒤에 해당 배열에 데이터를 넣어주는 방식입니다. 하지만 퀵정렬의 경우 기존의 배열을 수정하는 방식을 사용하기때문에 상대적으로 속도가 빠를 수 있습니다.

코드

• quick sort

  • def quicksort(arr):
        n = len(arr)
        qsort(arr, 0, n - 1)
    
    
    def qsort(arr, left, right):
        if left < right:
            p = partition(arr, left, right)
            qsort(arr, left, p - 1)
            qsort(arr, p + 1, right)
    
    
    def partition(arr, left, right):
        pivot = arr[right]
        idx = left
        for j in range(left, right):
            if arr[j] < pivot:
                arr[idx], arr[j] = arr[j], arr[idx]
                idx += 1
        arr[idx], arr[right] = arr[right], arr[idx]
        return idx
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    quicksort(arr)
    print(arr)

출처

• https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2870/
• https://imgur.com/gallery/omL5k