Chapter 35: Quicksort Challenges

Challenge 1: Iterative quicksort

지금까지 퀵 정렬(quick sort)을 재귀적(recursively)으로 구현했다. 이와 달리, 구분 전략(partition strategy)을 사용해 퀵 정렬을 반복적(iteratively)으로 구현할 수 있다.

 

Solution

Lomuto’s partition strategy를 사용해 구현한다. 해당 함수는 배열(Array)과 low와 high를 매개변수로 받는다. 스택(Stack)을 사용하여, start와 end의 value 쌍(pair)을 저장한다.

public func quicksortIterativeLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
    var stack = Stack<Int>() //index를 저장하는 stack을 생성한다.
    stack.push(low)
    stack.push(high)
    //stack에 하한(low)과 상한(high)를 push한다.
    
    while !stack.isEmpty { //stack이 비어 있으면, 퀵 정렬이 완료된 것이다.
        guard let end = stack.pop(), let start = stack.pop() else {
            //stack에서 시작(start)과 끝(end) index 쌍을 가져온다.
            continue
        }
        
        let p = partitionLomuto(&a, low: start, high: end)
        //현재의 start와 end index로 Lomuto’s partitioning을 실행한다.
        //Lomuto 알고리즘은 마지막 요소를 pivot으로 선택해, pivot보다 작은요소, pivot 보다 큰 요소로 3등분 한다.
        
        if (p - 1) > start { //분할이 완료되면, 하한의 start와 end index를 Stack에 추가하여 분할한다.
            stack.push(start)
            stack.push(p - 1)
        }
        
        if (p + 1) < end { //분할이 완료되면, 상한의 start와 end index를 Stack에 추가하여 분할한다.
            stack.push(p + 1)
            stack.push(end)
        }
    }
}

start와 end index 쌍을 스택(Stack)에 저장하여, 분할(partition)을 수행한다. 반복적으로(iterative) 구현한 퀵 정렬(quick sort)가 제대로 작동하는지 확인한다.

var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortIterativeLomuto(&list, low: 0, high: list.count - 1)

print(list) // [-1, 0, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

출력은 다음과 같다.

[-1, 0, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

---

Challenge 2: Merge sort or quicksort

퀵 정렬(quick sort)보다, 합병 정렬(merge sort)을 사용해야 할 때(when)와 그 이유(why)를 설명한다.

 

Solution

• 안정성(stability)이 필요한 경우, 퀵 정렬(quick sort) 보다 합병 정렬(merge sort)을 사용하는 것이 좋다. 합병정렬(merge sort)은 안정적인(stable) 정렬이며, O(n log n)을 보장한다. 퀵 정렬(quick sort)은 불안정 정렬이며, 최악의 경우 O(n²)의 성능을 보인다.

안정적인 정렬(Stable Sort)  : 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 (버블 정렬, 삽입 정렬)
불안정한 정렬(Unstable Sort)  : 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 (선택 정렬)

• 합병정렬(merge sort)은 요소(element)가 메모리에 분산되어 있는 큰 자료 구조(data structure)의 경우 적합하다. 퀵 정렬(quick sort)은 요소(element)가 인접한 블록에 저장되어 있을 때 가장 잘 작동한다.

---

Challenge 3: Partitioning with Swift standard library

Swift Standard Library의 partition(by:) 함수를 사용해, 퀵 정렬(quick sort)을 구현한다.

https://developer.apple.com/documentation/swift/array/3017524-partition
partition(by:)는 Collection을 재정렬하고, 해당 조건을 만족하는 첫 index를 반환한다. 따라서 반환되는 index 이전의 요소들은 해당 조건을 만족하지 않고, index 이후의 요소들은 해당 조건을 만족한다.

 

Solution

Collection에서 퀵 정렬(quick sort)을 수행하려면, 다음 사항을 충족해야 한다.

• Collection은 반드시 MutableCollection이어야 한다. 이를 구현해야 Collection 요소(element)의 값(value)를 변경할 수 있다.
• Collection은 반드시 BidirectionalCollection이어야 한다. 이를 구현해야, Collection을 앞 뒤로 순회(traverse)할 수 있다. 퀵 정렬(Quick sort)은 Collection의 first와 last의 index에 따라 달라진다.
• Collection의 요소(element)는 Comparable이어야 한다.

extension MutableCollection where Self: BidirectionalCollection, Element: Comparable {
    mutating func quicksort() {
        quicksortLumuto(low: startIndex, high: index(before: endIndex))
    }
    
    private mutating func quicksortLumuto(low: Index, high: Index) {
        //low, high index로 정렬을 시행한다.
        if low <= high { //start와 end의 index가 서로 겹칠 때까지 Collection에서 퀵 정렬을 한다.
            let pivotValue = self[high] //Lumuto 알고리즘은 Collection의 마지막 요소를 pivot으로 선택해 구분한다.
            var p = self.partition { $0 > pivotValue }
            //Collection의 요소를 분할하고, pivot 값보다 큰 첫 번째 index p 를 반환한다.
            //p 이전의 요소들은 조건을 만족시키지 않고, p 이후의 요소들은 조건을 만족시킨다.
            
            if p == endIndex { //p 가 마지막 index인 경우, before index로 이동한다.
                // [8 3 2 8]
                //        p
                //이런 경우에(p가 마지막 index인 경우), partition을 수행해도 변화가 없다.
                //p 이전의 요소는 partition을 만족시키지 않으므로, out of memory가 될때까지 재귀 loop에 빠진다.
                p = index(before: p)
            }
            
            self[..<p].quicksortLumuto(low: low, high: index(before: p))
            //pivotValue보다 크지 않은 요소로 구성된 첫 partition에서 퀵 정렬을 수행한다.
            self[p...].quicksortLumuto(low: index(after: p), high: high)
            //pivotValue보다 큰 요소로 구성된 두 번째 partition에서 퀵 정렬을 수행한다.
        }
    }
}

구현을 확인해 본다.

var numbers = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
print(numbers) // [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]

numbers.quicksort()
print(numbers) // [-1, 0, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

출력은 다음과 같다.

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
[-1, 0, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

partition(by:)의 구현을 살펴보면, _partitionImpl(by:)이 Hoare’s partition과 유사한 전략을 사용하는 것을 확인할 수 있다.
http://bit.ly/partitionimpl