Swift) 병합 정렬(합병 정렬/Merge Sort)

 

 

 

안녕하세요, UX를 고려하는 개발자 유자입니다!

실행시간 상한이 n^2인 선택 정렬과 버블 정렬을 알아봤는데요.

이번에는 실행시간 상한이 n^2가 아닌 병합 정렬에 대해서 알아보겠습니다.

 

 

 

 

 

 

1. 병합 정렬 예시

 

바로 예시부터 보면서 알아보겠습니다!

병합 정렬을 사용해서 아래 숫자들을 오름차순으로 정렬해 보겠습니다.

 

 

7 4 5 2 6 3 8 1

 

 

 

 

1. 원소가 한 개가 될 때까지 숫자들을 반으로 계속 나눕니다.

 

 

 

 

 

 

2. 왼쪽과 오른쪽 모두 원소가 1개 남아있으므로 두 원소를 병합합니다.

여기서 병합이란? 두 배열의 인덱스를 0부터 비교하며

가장 작은 값을 꺼내 임시 배열에 저장하는 것을 말합니다.

(아래 gif를 통해 더 상세하게 확인하실 수 있습니다!)

 

 

 

 

 

 

 

 

 

 

3. 왼쪽 절반(7, 4)을 정렬했으니 오른쪽 절반(5, 2)을 정렬할 차례입니다.
마찬가지로 원소가 1개 남아있을 때까지 반으로 나눈 뒤, 두 숫자를 병합합니다.

 

 

 

 

 

 

 

 

 

4. 왼쪽 절반(7,4) 오른쪽 절반(5,2) 모두 정렬했으니, 병합합니다.

 

 

 

 

 

 

5. 이제 원래 배열의 왼쪽을 모두 정렬했으니, 오른쪽을 정렬해야 합니다.

마찬가지로 원소가 1이 될 때까지 반으로 나눈 후,

원소가 1이 되면 두 숫자를 병합하는 과정을 반복합니다.

 

 

 

 

 

 

 

 

6. 이제 전체 배열의 왼쪽과 오른쪽이 모두 정렬되었으니 병합합니다.

 

 

 

 

전체 과정을 gif로 보면 다음과 같은 모습입니다.

 

 

출처: 위키백과

 

 

 

 

 

이러한 방식으로 정렬하는 방법을

병합정렬이라고 하고, 사전적 정의는 다음과 같습니다.

 

 

원소가 한 개가 될 때까지 계속 반으로 나눠 정렬 후

다시 합쳐나가는 정렬 방식

 

 

 

 

 

 

 

 

 

 

 

 

 

2. 병합 정렬 의사코드

 

다음은 병합 정렬의 의사코드입니다.

 

 

if 받은 입력에 원소가 하나라면
  return
else
  왼쪽 절반을 정렬한다.
  오른쪽 정렬을 정렬한다.
  두 배열을 병합한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 병합 정렬 시간 복잡도

병합정렬은 쪼개는 과정이 한 번 있을 때마다 병합하는 과정이 한 번씩 발생합니다.

따라서 무언가를 반으로 나누는 데 걸리는 시간(log n)과

반으로 나눈 부분을 다시 병합하는 시간(n)을 곱해줘야 합니다.

 

 

즉, 실행시간의 상한은 O(n log n)입니다.

 

 

무언가를 반으로 나누는 데 걸리는 시간이

왜 log n인지에 대한 설명은 해당 포스팅 참고 부탁드립니다.

 

 

 

 

 

 

 

 

 

 

 

4. 병합 정렬 구현해 보기

병합 정렬은 쪼개고, 병합하는 과정이 반복되는 만큼

함수가 본인 스스로를 호출해서 사용할 수 있도록 구현했습니다!

 

 

func mergeSort(_ arr: [Int]) -> [Int] {
    let count = arr.count
    guard count > 1 else { return arr }
    let mid = count / 2
    let left = mergeSort(Array(arr[0..<mid]))
    let right = mergeSort(Array(arr[mid..<count]))

    return merge(left, right)
}


//병합하는 함수
func merge(_ left:[Int], _ right:[Int]) -> [Int] {
    var indexL = 0
    var indexR = 0
    let countL = left.count
    let countR = right.count

    var result = [Int]()

    while countL > indexL && countR > indexR {
        if left[indexL] < right[indexR] {
            result.append(left[indexL])
            indexL += 1
        } else {
            result.append(right[indexR])
            indexR += 1
        }
    }

    if indexL < countL {
        result += left[indexL..<countL]
    }

    if indexR < countR {
        result += right[indexR..<countR]
    }

    return result
}

 

 

 

mergeSort함수는 배열의 크기가 1보다 클 때만 진행하고,

1보다 크지 않다면 현재 배열을 반환(return)합니다.

 

 

merge함수는 왼쪽 인덱스를 담당하는 indexL과

오른쪽 인덱스를 담당하는 indexR로

요소 하나씩 비교하여 더 작은 값을 result 배열에 추가합니다.

 

while문이 다 돌고 난 뒤, 왼쪽과 오른쪽에 남은 원소가 있다면

남은 원소를 result 배열에 추가합니다.

 

 

 

이렇게 정렬된 result를 반환하면 병합이 마무리됩니다.

 

 

 

 

---

 

 

 

병합정렬은 재귀 함수를 알고 있으면 훨씬 더 이해하기가 쉽습니다!