Chapter 26: O(n²) Sorting Algorithms

O(n²) 시간 복잡도(time complexity) 정렬 알고리즘(sorting algorithm)은 성능이 좋지는 않지만, 이해하기 쉽고 일부 시나리오에서는 유용하게 사용할 수 있다. 이러한 알고리즘(algorithm)은 공간 효율적이며, 상수(constant, 일정한) O(1) 추가 메모리 공간만 필요로 한다. 작은 데이터 세트의 경우, 이러한 정렬 알고리즘은 보다 복잡한 정렬 알고리즘 보다 훨씬 효과적일 수 있다. 대표적인 O(n²) 정렬 알고리즘은 다음과 같다.

• 거품 정렬(Bubble sort)
• 선택 정렬(Selection sort)
• 삽입 정렬(Insertion sort)

이 알고리즘(algorithm) 모두 비교 기반(comparison-based) 정렬 방법이다. 요소(element) 정렬을 위해 less-than operator(<) 등을 사용한다. 이런 비교가 호출되는 횟수로 정렬기법의 일반적인 성능을 측정한다.

 

Bubble sort

가장 간단한 정렬 중 하나인 거품 정렬(bubble sort)은 인접 값(value)을 반복적으로 비교하고, 필요한 경우 이를 교환하여 정렬을 수행한다. 따라서 큰 값을 가진 요소일 수록(내림 차순 정렬일 경우에는 반대로 작은 값일 수록) Collection의 끝까지 "bubble up" 된다.

 

Example

다음과 같은 카드가 있다고 가정한다.

 

거품 정렬(bubble sort) 알고리즘(algorithm)의 단일 패스(single pass)는 다음과 같이 구성된다.

• Collection의 시작 부분에서 부터 시작한다. 9와 4를 비교해 보면, 큰 값이 앞서 나오므로 교환(swap)이 필요하다. 따라서, 교환 이후 Collection은 [4, 9, 10, 3]이 된다.
• Collection의 다음 index로 이동한다. 9와 10일 비교해 보면 순서대로 되어 있다.
• Collection의 다음 index로 이동한다. 10과 3을 비교해 보면, swap이 필요하다. 따라서 Collection은 [4, 9, 3, 10]이 된다.

단일 패스(single pass)를 완료해도, 전체 Collection이 완전히 정렬되는 경우는 거의 없다. 그러나 최대값(10)이 Collection의 끝으로 "bubble up" 되었다. 이후 다음 패스(pass)는 다시 첫 번째 index에 대해 동일하게 진행된다.

 

교환(swap)하지 않고도 Collection 전체를 pass 할 수 있을 때 거품 정렬(bubble sort)은 완료된다. 최악의 경우 n-1 번의 pass가 필요하며, 여기서 n은 Collection의 요소(element) 수 이다.

 

Implementation

public func bubbleSort<Element>(_ array: inout [Element]) where Element: Comparable {
    guard array.count >= 2 else { //2개 이하의 요소를 가지고 있으면 정렬할 필요가 없다.
        return
    }
    
    for end in (1..<array.count).reversed() { 
        //single pass는 Collection의 끝으로 가장 큰 value를 버블링 한다.
        //모든 pass는 이전 pass보다 하나 더 적은 수의 비교를 수행하므로(pass가 끝날 때마다 큰 값 순으로 하나씩 완전히 정렬된다),
        //기본적으로 각 pass마다 Array를 하나씩 줄인다.
        var swapped = false
        
        for current in 0..<end { //이 loop는 단일 pass를 수행한다.
            if array[current] > array[current + 1] { //인접한 값을 비교하고 필요한 경우 swap한다.
                array.swapAt(current, current + 1)
                swapped = true
            }
        }
        
        if !swapped { //해당 pass에서 교환한 값이 없다면, Collection이 완전히 정렬된 것이므로 빠르게 반환할 수 있다.
            return
        }
    }
}

구현을 확인해 본다.

example(of: "bubble sort") {
    var array = [9, 4, 10, 3]
    
    print("Original: \(array)") 
    // Original: [9, 4, 10, 3]
    
    bubbleSort(&array)
    
    print("Bubble sorted: \(array)") 
    // Bubble sorted: [3, 4, 9, 10]
}

출력은 다음과 같다.

---Example of bubble sort--- 
Original: [9, 4, 10, 3] 
Bubble sorted: [3, 4, 9, 10]

이미 정렬되어 있는 경우 거품 정렬(bubble sort)의 시간 복잡도(time complexity)는 O(n)으로 최선(best)이다. 최악(worst)과 평균(average)의 경우 시간 복잡도(time complexity)는 O(n²)으로 가장 매력적이지 않은 정렬 알고리즘 중 하나이다.

 

Selection sort

선택 정렬(selection sort)은 거품 정렬(bubble sort)의 기본 개념을 따르지만, swapAt 연산(operation) 횟수를 줄여 알고리즘(algorithm)을 개선한다. 선택 정렬(Selection sort)은 각 패스(pass)의 끝에서만 교환(swap) 한다.

 

Example

다음과 같은 카드가 있다고 가정한다.

 

선택 정렬(selection sort)은 각 패스(pass)에서 정렬되지 않은 가장 작은 값(오름차순 기준)을 찾아 제자리로 교환(swap) 한다.

1. 3이 가장 작은 값이므로 9와 교환(swap)한다. [3, 4, 10, 9]
2. 그다음 가장 작은 값은 4이다. 정렬된 위치에 있으므로 그대로 둔다. [3, 4, 10, 9]
3. 마지막으로 9와 10을 교환(swap)한다. [3, 4, 9, 10]

 

 

Implementation

public func selectionSort<Element>(_ array: inout [Element]) where Element: Comparable {
    guard array.count >= 2 else {
        return
    }
    
    for current in 0..<(array.count - 1) { 
        //마지막 요소를 제외한 Collection의 모든 요소에 대해 pass를 수행한다.
        //다른 모든 요소가 올바르게 정렬되어 있다면, 마지막 요소도 포함되므로, 여기에 마지막 요소를 포함할 필요는 없다.
        var lowest = current
        
        for other in (current + 1)..<array.count { 
            //모든 pass마다, 남은 Collection에서 가장 작은 값을 가진 요소를 찾는다.
            if array[lowest] > array[other] {
                lowest = other
            }
        }
        
        if lowest != current { 
            //해당 요소가 current가 아닌 경우 swap 한다. //current가 최소값이 아닌 경우
            array.swapAt(lowest, current)
        }
    }
}

구현을 확인한다.

example(of: "selection sort") {
    var array = [9, 4, 10, 3]
    
    print("Original: \(array)") 
    // Original: [9, 4, 10, 3]
    
    selectionSort(&array)
    
    print("Selection sorted: \(array)") 
    // Selection sorted: [3, 4, 9, 10]
}

출력은 다음과 같다.

---Example of selection sort---
Original: [9, 4, 10, 3]
Selection sorted: [3, 4, 9, 10]

거품 정렬(bubble sort)과 마찬가지로 선택 정렬(selection sort)은 최선(best), 최악(worst), 평균(average) 시간 복잡도(time complexity) 모두 O(n²)이다(거품 정렬에선 이미 정렬된 경우에만 O(n)이다). 좋지 않은 성능이지만, 이해하기 쉽고 거품 정렬(bubble sort)보다는 성능이 좋다.

 

Insertion sort

삽입 정렬(insertion sort)은 더 유용하다. 거품 정렬(bubble sort), 선택 정렬(selection sort)과 마찬가지로 시간 복잡도(time complexity)는 O(n²)이지만, 성능은 더 뛰어날 수 있다. 삽입 정렬(insertion sort)은 데이터가 정렬되어 있을수록 해야할 작업이 적어진다. 데이터가 이미 정렬된 경우, 삽입 정렬의 시간 복잡도는 O(n)이다. 스위프트 표준 라이브러리(Swift standard library)의 정렬(sort) 알고리즘(algorithm)은 정렬되지 않은 작은(20개 이하의 요소) partition의 경우, 삽입 정렬(insertion sort)을 응용한 하이브리드(hybrid) 방식을 사용한다.

 

Example

삽입 정렬(insertion sort)은 카드를 분류하는 것과 비슷하다. 다음과 같은 카드가 있다고 가정한다.

 

삽입 정렬(insertion sort)은 왼쪽에서 오른쪽으로 반복된다. 각각의 요소(element)는 정확한 위치에 도달할 때까지 왼쪽으로 이동한다.

 

1. 비교할 이전의 요소가 없기 때문에, 첫 번째 요소를 무시한다. [9, 4, 10, 3]
2. 4와 9를 비교하여 4를 왼쪽으로 바꾸면서 9와 위치를 교환(swap)한다. 이미 정렬된 부분과 비교해서 맞는 위치에 삽입한다. [4, 9, 10, 3]
3. 10은 이전 요소와 비교해 올바른 위치에 있으므로 이동할 필요가 없다. [4, 9, 10, 3]
4. 마지막으로 3을 각각 10, 9, 4와 비교하고 교환(swap)하여 가장 앞으로 이동시킨다. [3, 4, 9, 10]

삽입 정렬(insertion sort)에서 최상(best)의 경우는 이미 정렬된 경우이며, 이때는 왼쪽 이동(shift)이 필요하지 않다.

 

Implementation

public func insertionSort<Element>(_ array: inout [Element]) where Element: Comparable {
    guard array.count >= 2 else {
        return
    }
    
    for current in 1..<array.count { //삽입 정렬은 왼쪽에서 오른쪽으로 한 번 반복해야 한다.
        for shifting in (1...current).reversed() { 
            //current index를 역으로 하여, 필요할 때 왼쪽으로 shifting 할 수 있다.
            if array[shifting] < array[shifting - 1] { 
                //필요한 만큼 요소를 왼쪽으로 계속 이동 시킨다.
                array.swapAt(shifting, shifting - 1)
            } else { 
                //요소가 제자리에 오면, loop를 종료하고 다음 요소를 시작한다.
                break
            }
        }
    }
}

구현을 확인해 본다.

example(of: "insertion sort") {
    var array = [9, 4, 10, 3]
    
    
    print("Original: \(array)") 
    // Original: [9, 4, 10, 3]
    
    insertionSort(&array)
    
    print("Insertion sorted: \(array)") 
    // Insertion sorted: [3, 4, 9, 10]
}

출력은 다음과 같다.

---Example of insertion sort---
Original: [9, 4, 10, 3]
Insertion sorted: [3, 4, 9, 10]

삽입 정렬(insertion sort)은 데이터가 이미 정렬되어 있는 경우 가장 빠른 알고리즘(algorithm) 중 하나이다. 정렬이 되어 있는 경우 빠르다는 것이 당연하다고 생각할 수 있지만, 모든 정렬 알고리즘(sorting algorithm)이 그런 것은 아니다. 실제로 대부분의 요소(element)가 이미 정렬되어 있는 경우, 삽입 정렬(insertion sort)은 상당히 좋은 성능을 보인다.

 

Generalization

배열(Array) 이외의 Collection에서도 사용할 수 있도록 정렬 알고리즘(sorting algorithm)을 일반화(generalize)한다. 하지만, 어떤 Collection type을 사용하는지는 알고리즘(algorithm)에 따라 달라진다.

• 삽입 정렬(Insertion sort)은 요소(element)를 이동할 때, Collection을 역방향(backward)으로 순회(traverse)한다. 따라서, collection은 반드시 BidirectionalCollection type이어야 한다.
• 거품 정렬(Bubble sort)과 선택 정렬(Selection sort)은 Collection을 시작에서 끝으로 일방향으로만 순회(traverse)하므로, 모든 Collection type에서 사용할 수 있다.
• 모든 경우에, 요소를 교환(swap)해야 하므로 MutableCollection type이어야 한다.

거품 정렬(Bubble sort)을 업데이트 한다.

public func bubbleSort<T>(_ collection: inout T) where T: MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    
    for end in collection.indices.reversed() {
        var swapped = false
        var current = collection.startIndex
        
        while current < end {
            let next = collection.index(after: current)
            
            if collection[current] > collection[next] {
                collection.swapAt(current, next)
                swapped = true
            }
            
            current = next
        }
        
        if !swapped {
            return
        }
    }
}

알고리즘(algorithm)은 동일하게 유지된다. Collection의 index를 사용하도록 loop를 업데이트하면 된다. 다음으로 선택 정렬(Selection sort)을 업데이트 한다.

public func selectionSort<T>(_ collection: inout T) where T: MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    
    for current in collection.indices {
        var lowest = current
        var other = collection.index(after: current)
        
        while other < collection.endIndex {
            if collection[lowest] > collection[other] {
                lowest = other
            }
            
            other = collection.index(after: other)
        }
        
        if lowest != current {
            collection.swapAt(lowest, current)
        }
    }
}

삽입 정렬(Insertion sort)을 업데이트 한다.

public func insertionSort<T>(_ collection: inout T) where T: BidirectionalCollection & MutableCollection, T.Element: Comparable {
    guard collection.count >= 2 else {
        return
    }
    
    for current in collection.indices {
        var shifting = current
        
        while shifting > collection.startIndex {
            let previous = collection.index(before: shifting)
            
            if collection[shifting] < collection[previous] {
                collection.swapAt(shifting, previous)
            } else {
                break
            }
            
            shifting = previous
        }
    }
}

약간의 코드 변경으로 알고리즘(algorithm)을 일반화할 수 있다. 

 

Key points

• n² 알고리즘(algorithms)은 대부분 좋지 않은 성능을 보이지만, 특정 상황에서는 뛰어난 성능을 보일 수 있다. 삽입 정렬(insert sort)의 경우 collection이 이미 정렬되어 있는 경우 O(n)으로 좋은 성능을 보이지만, 정렬되지 않은 데이터가 늘어나면 O(n²)으로 점점 성능이 나빠진다.
• 삽입 정렬(insert sort)은 대부분의 데이터가 정렬되 있다는 것을 미리 알고 있는 상황에서 가장 성능이 좋은 정렬 알고리즘(sorting algorithm) 중 하나이다.