[정렬] 병합정렬 Swift

병합정렬

---

핵심

• 나누기 : 배열을 원소가 1개 남을때 까지 반으로 쪼갠다.
• 정렬 & 합치기 : 왼쪽과 오른쪽으로 쪼개진 배열을 비교해서 하나의 배열로 합친다.

출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

Swift 코드

// 참고 : 아이작 코드로 공부했다. v 재귀함수 동작에 대해 공부할 필요성을 느꼇다.

import Foundation

//이때 l과 r은 정렬이 된 상태여야 한다.
func merged(l: [Int], r: [Int]) -> [Int] {
    var currentLeftIndex = 0
    var currentRightIndex = 0
    var sorted = [Int]()

    //왼쪽 오른쪽 배열을 비교해서 큰 숫자 차례로 담음
    while currentLeftIndex < l.count && currentRightIndex < r.count {
        if l[currentLeftIndex] > r[currentRightIndex] {
            sorted.append(l[currentLeftIndex])
            currentLeftIndex += 1
        } else {
            sorted.append(r[currentRightIndex])
            currentRightIndex += 1
        }
    }

    //아직 끝나지 않은 배열을 뒤에 붙임
    if currentLeftIndex < l.count {
        sorted.append(contentsOf: l[currentLeftIndex...])
    }
    if currentRightIndex < r.count {
        sorted.append(contentsOf: r[currentRightIndex...])
    }

    return sorted
}

func mergeSort(arr: [Int]) -> [Int] {
    if arr.count <= 1 {
        return arr
    }
    let mid = arr.count / 2
    let leftArr = Array(arr[0..<mid])
    let rightArr = Array(arr[mid..<arr.count])

    //1개 남을때 까지 계속 재귀적으로 반으로 쪼갬
    let sortedLeftArr = mergeSort(arr: leftArr)
    let sortedRightArr = mergeSort(arr: rightArr)

    //합치기
    return merged(l: sortedLeftArr, r: sortedRightArr)
}

print(mergeSort(arr: [3, 1, 2, 4, 1, 5, 3, 2]))

시간복잡도

순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = log₂n * n

출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

합병 단계의 수 (깊이)

log₂n 개

각 합경 단계의 비교 연산

n번 비교

이동 횟수

임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.
순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동 연산 = 2nlog₂n

결론

T(n) = nlog₂n(비교) + 2nlog₂n(이동) = 3nlog₂n = O(nlog₂n)