퀵 정렬 (Quick Sort)

목표

• 퀵 정렬(quick sort)에 대해 설명할 수 있다.
• 퀵 정렬(quick sort) 과정에 대해 설명할 수 있다.
• 퀵 정렬(quick sort)를 Kotlin으로 구현할 수 있다.
• 퀵 정렬(quick sort) 의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.

요약

합병 정렬과 같이 분할 정복 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 합병정렬과는 달리 리스트를 비균등하게 분할한다.

• 분할 정복 (divide and conquer) 방법
  • 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
  • 대개 순환 호출을 이용하여 구현한다.

과정 (오름차순)

1. 리스트 안에 있는 한 요소(피벗)을 선택한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   1. 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복한다.
   2. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
   1. 리스트의 크기가 0이나 1이 될 때까지 반복

Kotlin 코드

fun quickSort(array: MutableList<Int>, low: Int, high: Int) {
    if (high <= low) return

    val mid = partition(array, low, high)
    quickSort(array, low, mid - 1)
    quickSort(array, mid, high)
}

fun partition(array: MutableList<Int>, low: Int, high:Int): Int {
    val pivot = array[(low + high) / 2]
    var left = low
    var right = high
    while (left <= right) {
        while (array[left] < pivot) {
            left++
        }
        while (array[right] > pivot) {
            right--
        }
        if (left <= right) {
            val temp = array[left]
            array[left] = array[right]
            array[right] = temp
            left++
            right--
        }
    }
    return left
}

Python 코드

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

    return sort(0, len(arr) - 1)

시간 복잡도

1. 최악의 경우 : 피벗 값이 항상 최댓값이거나 최솟값인 경우

2. 최선의 경우 : 피벗 값이 항상 중간값일 경우

공간 복잡도

기존에 주어진 배열에서 원소 Swap만 이루어지므로 공간 복잡도는 O(n)인 것 같은데 O(log n)이라는데도 있고 잘 모르겠다..

특징

장점

1. 속도가 빠르다. (O(N log N)의 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
2. 주어진 배열에서만 교환하므로 다른 메모리 공간이 필요하지 않다. => 제자리 정렬(in-place sorting)

단점

1. 정렬된 리스트에 대해서는 수행시간이 오래 걸린다.(최악의 경우 : O(N^2))
2. 불안정 정렬이다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

퀵 정렬 개선 방법

1. 난수 분할 : Pivot을 매번 Random한 위치에서 잡는 방법
2. 배열의 가장 첫 인덱스, 끝 인덱스, 중간 인덱스에 해당하는 값들을 정렬하여 중간값을 Pivot으로 사용하는 방법
3. 삽입 정렬과 함께 사용 : Array의 길이가 특정 수 이하라면 삽입 정렬을 사용하고 크다면 퀵 정렬을 사용하는 방법

Reference

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/QuickSort.md
• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
• https://gusdnd852.tistory.com/124