[알고리즘] 5강 빠른 정렬(Quick Sort)

빠른 정렬은 분할정복법으로 한다. merge와 비슷하지만 다른 점은 합병 단계에 아무것도 하지 않는 다는 것이다.

분할정복법

• 분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.
  elements in lower parts ≤ elements in upper parts
  • 기준을 pivot 이라 하고 해당 값을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 오도록 한다.
• 정복 : 각 부분을 순환적으로 정렬한다. (recursive)
• 합병 : nothing to do (아무것도 하지 않음)
  • 정복 작업을 하게 되면 전체가 정렬된 것으로 본다

시간복잡도

• 평균 - O(NlogN) / 최악 - O(n^2)

의사 코드로 표현하기(pseudo-code)

    /// data[p...r] 원소를 정렬한다.
    func quickSort(data: [Int], p: Int, r: Int) {
        // 1. 데이터를 분할한다.
        // 2. 왼쪽 부분배열 정렬
        // 3. 오른쪽 부분배열 정렬
    }

    /// pivot을 기준으로 분할한 후 pivot의 위치값을 return 한다.
    func partition(data: [Int], p: Int, r: Int) -> Int {
        // 1. A[j] 와 pivot을 비교한다.
        // 2. A[j] > pivot 이면?
            // 2-1. j를 1 증가한다.
        // 3. A[j] <= pivot 이면?
            // 3-1. i를 1 증가한다.
            // 3-2. swap A[i], A[j]
            // 3-3. j를 1 증가한다.
        // 4. j가 배열 끝까지 갈 때 까지 2~4번 과정을 반복한다.
        // 5. swap A[i+1], pivot 
        // 6. return pivot 자리 값
    }

Swift Code

    /// 4. Quick Sort
    func quickSort(data: inout [Int], p: Int, r: Int) {
        if p < r {
            let q = partition(data: &data, p: p, r: r)
            quickSort(data: &data, p: p, r: q - 1)
            quickSort(data: &data, p: q + 1, r: r)
        }
    }

    func partition(data: inout [Int], p: Int, r: Int) -> Int {
        let pivot = data[r]
        var i = p - 1
        var j = p

        while j <= r - 1 {
            if data[j] >= pivot {
                j += 1
            } else {
                i += 1
                data.swapAt(i, j)
                j += 1
            }
        }

      data.swapAt(i + 1, r)
        return i + 1
    }

    var data = [31, 8, 48, 73, 11, 3, 20, 29, 65, 15]
    quickSort(data: &data, p: 0, r: 9)
    print(data)

https://github.com/devssun/Algorithm-Study/blob/master/Algorithm/Inflearn/Algorithm-Inflearn/main.swift

---

Pivot 선택 기준

1. 첫번째 값이나 마지막 값을 피봇으로 선택 (위의 예제)

• 이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
• 현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높다

2. "Median of Three"

• 첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 피봇으로 선택
• 최악의 경우 시간복잡도가 달라지지는 않음

3. Randomized Quicksort

• 피봇을 랜덤하게 선택
• no worst case instance, but worst case execution
• 평균 시간복잡도 : O(NlogN)