Swift 합병 정렬 해보기 (Merge Sort)

Swift 합병 정렬 해보기 (Merge Sort)

 

오늘은 분할 정복중에서 합병 정렬에 대하여 알아보겠습니다.

 

 

 

합병 정렬이란?

합병 정렬은 이전 포스팅에서 알아보았던 분할 정복중 하나로 마찬가지로 재귀 함수를 이용해서 분할을 합니다.

 

합병 정렬의 과정은 다음과 같습니다.

 

1 ) 리스트의 길이가 0 혹은 1이면 이미 정렬된 리스트로 간주합니다.

 

2 ) 그렇지않은 리스트는 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눕니다.

 

3 ) 각 부분 리스트를 재귀적으로 합병 정렬을 이용하여 정렬합니다.

 

4 ) 두 부분 리스트를 다시 합병하여 정렬된 리스트로 만듭니다.

 

라는 과정을 걸치게 됩니다.

 

합병 정렬도 퀵 정렬과 마찬가지로 분할 / 정복 / 결합 의 과정을 걸칩니다.

 

다음과 같은 정렬이 있습니다.

 

 

 

1) 해당 배열을 반으로 쪼갭니다.

 

2) 리스트의 크기가 0 또는 1이 아니므로 한번 더 나눕니다.

3) 리스트의 크기가 0 또는 1이 아니므로 한번 더 나눕니다.

 

4) 리스트의 크기가 1이 되었으므로 나누기를 멈추고, 가장 작은 단위의 인접한 배열끼리 비교, 결합한다.

 

5) 4번의 과정을 2개의 리스트만이 남을때 까지 반복한다.

 

 

6) 5번 과정을 통해 2개의 리스트가 남게 되었다면 2개의 정렬된 리스트를 합병(Merge)한다.

 

※※※ 합병 과정 ※※※

 

위에 배열을 예시로 계속 이어서 설명하겠습니다.

위 사진처럼 합병과정을 앞둔 두개의 리스트가 있습니다.

 

2개의 리스트의 값들을 처음부터 하나씩 비교합니다.

 

왼쪽 리스트의 첫값은 1, 오른쪽 리스트의 첫번째 값은 3이군요.

 

1과 3을 비교했을 때 1이 더 작습니다. 이때 더 작은값 1을 새로운 리스트에 넣고 계속 비교를 이어갑니다.

 

 다시 왼쪽의 값 2와 오른쪽의 값 3을 비교합니다.

 

2가 3보다 작으므로 새로운 리스트에 2가 들어가고 비교를 이어갑니다.

 

해당 과정을 계속 진행하다가 먼저 하나의 리스트가 텅 비게 된다면 남은 하나의 리스트를 그대로 남은 자리에

 

붙여넣습니다.

 

이 처럼 최종적으로 합병된 리스트는 오름차순으로 정렬된 리스트가 나오게됩니다.

 

 

 

 

합병 정렬 코드로 구현해보기

func mergeSort(_ array: [Int]) -> [Int] {
    if array.count <= 1 { return array }
    let center = array.count / 2
    let left = Array(array[0..<center])
    let right = Array(array[center..<array.count])
    
    func merge(_ left: [Int],_ right: [Int]) -> [Int] {
        var left = left
        var right = right
        var result: [Int] = []
        
        while !left.isEmpty && !right.isEmpty {
            if left[0] < right[0] {
                result.append(left.removeFirst())
            } else {
                result.append(right.removeFirst())
            }
        }
        
        // 왼쪽 배열의 요소가 남은 경우
        if !left.isEmpty {
            result.append(contentsOf: left)
        }
        
        // 오른쪽 배열의 요소가 남은 경우
        if !right.isEmpty {
            result.append(contentsOf: right)
        }
        
        return result
    }
    
    return merge(mergeSort(left), mergeSort(right))
}

 

 

합병정렬의 시간복잡도는 O(n log n)로 퀵정렬과 동일하게 다른 정렬법보다 빠릅니다!