정렬 알고리즘

삽입 정렬 (insertion sort) - O(n2)

• 대상의 규모가 크지 않거나 어느 정도 정렬이 되어 있는 경우에는 O(n logN)인 병합 정렬 보다 높은 성능을 낼 수 있다
• Comparable 프로토콜에 부합하면 어떤 타입도 가능

func insertionSort<T: Comparable>(_ list: inout [T]) {
    if list.count <= 1 { return }
    for i in 1..<list.count {
        let x = list[i]
        var j = i
        while j > 0 && list[j-1] > x {
            list[j] = list[j-1]
            j -= 1
        }
        list[j] = x
    }
}

병합 정렬 (merge sort)

• 합병 정렬, 머지 소트
• 분할 정복 (Divide and Conquer Algorithm)을 활용

분할 (Divide)

• 컬렉션의 크기가 0 또는 1 이 될떄 까지 분할을 진행 (S = S1 + S2)

정복 (Conquer)

• S1과 S2를 재귀적으로 나눠서 (요소의 수가 1인) 베이스 케이스 단계까지 나눈 뒤 정렬을 시작

결합 (Combine)

• S1과 S2의 하위 목록을 병합해서 정렬된 시퀀스로 만든뒤 이를 다시 반환

func mergeSort<T: Comparable>(_ list: [T]) -> [T] { // 분할, 결합
    if list.count < 2 { return list }
    let center = list.count / 2
    let S1 = [T](list[..<center])
    let S2 = [T](list[center...])
    return merge(mergeSort(S1),mergeSort(S2))
}
func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] { // 정복(정렬)
    var mergeList: [T] = []
    var leftIdx: Int = 0
    var rightIdx: Int = 0
    // 정렬해서 mergeList에 담음
    while leftIdx < left.count && rightIdx < right.count {
        if left[leftIdx] < right[rightIdx] {
            mergeList.append(left[leftIdx])
            leftIdx += 1
        }else if right[rightIdx] < left[leftIdx] {
            mergeList.append(right[rightIdx])
            rightIdx += 1
        }else {
            mergeList.append(left[leftIdx])
            mergeList.append(right[rightIdx])
            leftIdx += 1
            rightIdx += 1
        }
    }
    // 남은거는 그냥 뒤에 붙임
    mergeList += [T](left[leftIdx..<left.count])
    mergeList += [T](right[rightIdx..<right.count])
    return mergeList
}

신속 정렬 (quick sort) - O(n log N)

• 인플레이스 정렬 기법을 사용해서 효율성이 높음
• 평균 시간은 O(n log N), 최악의 경우 O(n2)까지 길어질 수 있음
• 파티션 스킴(partitioning scheme)에 의한 피봇(pivot) 규칙에 따라 초기 배열을 하위 시퀀스, 상위 시퀀스 등 두개의 서브시퀀스로 나눔

로무토의 신속 정렬

• 이해하기는 쉬운 방법
• 효율성 측면에서 조금 아쉽다

func quickSort<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) { // lo: 첫 인덱스, hi: 마지막 인덱스
    if lo < hi { // 정상적인 범위이면
        let pivot = partition(&list, lo: lo, hi: hi)
        quickSort(&list, lo: lo, hi: pivot-1) // lo ~ pivot 전
        quickSort(&list, lo: pivot+1, hi: hi) // pivot 후 ~ hi
    }
}
// 정렬을 해주고 pivot의 위치를 반환
func partition<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) -> Int {
    let pivot = list[hi] // pivot으로 할 값을 잡아두고
    var i = lo // pivot보다 큰 값의 위치
    //pivot 보다 작은 값은 큰값 보다 앞으로 보냄
    for j in lo..<hi {
        if list[j] <= pivot {
            list.swapAt(i, j) // 큰값중 가장 앞 자리에 작은 값을 옮겨놓음
            i += 1
        }
    }
    list.swapAt(i, hi) // 현 상황에서 i는 pivot보다 큰값중 인덱스가 가장 작은 수, pivot과 자리를 바꿈 -> pivot보다 앞쪽은 작은수 뒷쪽은 큰수
    return i // pivot의 위치를 반환
}

호어의 신속 정렬

• 로무토에 비해 조금 더 복잡하다
• 평균적으로 요소의 교환 횟수가 세 배나 적고, 배열 요소가 모두 같을 때도 효율적으로 파티션을 만들어 낸 다는 장점이 있다

func HoareQuickSort<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) {
    if lo < hi { // 정상적인 범위면
        let pivot = HoarePartition(&list, lo: lo, hi: hi)
        HoareQuickSort(&list, lo: lo, hi: pivot) // lo ~ pivot (호어는 피봇까지 인걸 주의)
        HoareQuickSort(&list, lo: pivot+1, hi: hi) // pivot 후 ~ hi
    }
}
func HoarePartition<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) -> Int {
    let pivot = list[lo]
    var i = lo - 1
    var j = hi + 1
    while true {
        i += 1
        while list[i] < pivot { i += 1 } // 피봇보다 크거나 같으면 멈춤
        j -= 1
        while list[j] > pivot { j -= 1 } // 피봇보다 작거나 같으면 멈춤
        if i >= j { return j } //멈출때까지 갔는데 서로 지나쳤으면 j위치 반환 - [j]가 [i] 보다 작아서 : pivot을 [lo]로 하기 때문
        list.swapAt(i, j) // 멈출때 까지 갔는데 서로 안 지나쳤으면 [i]는 큰값 [j]는 작은값 이므로 둘이 바꾸고 계속 진행
    }
}

잘못된 피봇 선택 방식

1. 위의 두 코드는 임의로 피봇을 첫번째 요소 또는 마지막요소로 진행했는데 이렇게 될 경우 높은 성능을 기대하기 어렵다 => 실제로 처리할 데이터들의 대부분은 어느 정도 정렬된 데이터 이기 때문
2. 그렇다면 임의로 선택하는 방식은 어떨까? => 물론 처음과 마지막요소를 선택하는 것 보단 나을 수도 있다, 하지만 생각을 해야할 부분이 임의로 선택을 하기 위한 난수 발생기 또한 시간과 자원을 소모하며 이때 발생한 난수가 진정한 의미에서 난수 일지도 고민해봐야한다.

올바른 피봇 선택 방식 (세 수의 중앙값 전략)

• 해당 방법은 전체 요소의 중앙값을 선택하는것 보다 빠름
• 피봇이 최솟값 과 최대값인 요소일 가능성을 차단할 수 있음
• 중앙값을 선택하면서 좌,우, 중앙 요소를 정렬 할 수도 있다. 이때 가장 좌측은 피봇보다 작다는 사실과 가장 우측은 피봇보다 크다는 사실을 미리 알 수 있다.

func HoareQuickSort<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) {
    if lo < hi { // 정상적인 범위면
        let median = getMedianOfThree(&list, lo: lo, hi: hi)
        let pivot = HoarePartition(&list, lo: lo, hi: hi,median: median)
        HoareQuickSort(&list, lo: lo, hi: pivot) // lo ~ pivot (호어는 피봇까지 인걸 주의)
        HoareQuickSort(&list, lo: pivot+1, hi: hi) // pivot 후 ~ hi
    }
}
func HoarePartition<T: Comparable>(_ list: inout [T], lo: Int, hi: Int, median: T) -> Int {
    let pivot = median // 피봇을 중앙값으로 진행
    var i = lo - 1
    var j = hi + 1
    while true {
        i += 1
        while list[i] < pivot { i += 1 } // 피봇보다 크거나 같으면 멈춤
        j -= 1
        while list[j] > pivot { j -= 1 } // 피봇보다 작거나 같으면 멈춤
        if i >= j { return j } //멈출때까지 갔는데 서로 지나쳤으면 j위치 반환 - [j]가 [i] 보다 작아서 : pivot을 [lo]로 하기 때문
        list.swapAt(i, j) // 멈출때 까지 갔는데 서로 안 지나쳤으면 [i]는 큰값 [j]는 작은값 이므로 둘이 바꾸고 계속 진행
    }
}
func getMedianOfThree<T: Comparable>(_ list: inout [T], lo: Int, hi: Int) -> T {
    let center: Int = lo + (lo + hi) / 2
    if list[lo] > list[center] { list.swapAt(lo, center) }
    if list[lo] > list[hi] { list.swapAt(lo, hi)}
    if list[center] > list[hi] { list.swapAt(center, hi) }
    list.swapAt(center, hi) //일부러 바꿔둠 - 미리 정렬되어 있어도 순서를 바꿔놓음
    return list[hi] // 사실상 중앙값
}