[Algorithm] 합병 정렬(Merge Sort)란? (feat. Swift)

안녕하세요 Foma 💻 입니다!

오늘은 분할 정복 알고리즘 중 하나인 합병 정렬에 대해서 알아보려고 합니다.

 

바로 시작할게요~

---

분할 정복(Divide and Conquer Algorithm) 알고리즘이란? 🏡

 

위에서 합병 정렬은 분할 정복 알고리즘 중 하나라고 말씀드렸는데요.

 

그렇다면 분할 정복 알고리즘은 무엇일까요?

 

말 그대로 지금 해결할 수 없는 문제를 작게 쪼개서(분할) 풀어나가는(정복) 것입니다.

 

작은 문제를 해결하여 큰 문제를 해결해나가는 알고리즘으로 재귀 함수를 통해 자연스럽게 구현할 수 있습니다.

---

합병 정렬이란? 🤼‍♀️

 

합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다.
일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 
존 폰 노이만이 1945년에 개발했다. - 위키 백과 -

 

간단하게 설명드리면, 정렬되지 않은 리스트를 1개만 남을 때까지 반으로 분할한 다음

 

나눠진 리스트들을 서로 비교하며 합쳐가는 정렬 방식입니다.

---

합병 정렬 과정

 

만약 4,1,7,5,3,2,6 이렇게 정렬되지 않은 숫자들이 있다고 가정하겠습니다.

 

분할

 

먼저 이 숫자들을 반드로 나눕니다.

 

(4,1,7,5) - (3,2,6) 으로 나눠지겠죠?

 

이렇게 나눠진 숫자들을 하나만 남을 때까지 나눠줍니다.

 

(4,1) - (7,5)     (3,2) - (6) 

 

(4) - (1)   (7)- (5)   (3) - (2)   (6) 이렇게 나눠지겠죠?

 

합병

 

먼저 왼쪽부터 4 와 1을 비교해서 더 작은 숫자를 왼쪽으로 합쳐줍니다.

 

1,4 가 되겠죠?

 

이렇게 2개의 숫자를 비교해서 더 작은 숫자로 합병해줍니다.

 

(1,4) - (5,7) - (2,3) - (6)

 

그 다음 2개씩 합쳐준 숫자들을 비교해서 더 작은 숫자로 합병해줍니다.

 

1,4 와 5,7을 1,4,5,7로 합쳐줍니다.

 

2,3 과 6을 2,3,6으로 합쳐줍니다.

 

마지막으로 1,4,5,7과 2,3,6을 합쳐주면 1,2,3,4,5,6,7 로 정렬되게 됩니다.

 

아래 그림으로 보시면 이해가 훨씬 쉽게 되실거에요.

 

출처:알고리즘 도감

---

시간복잡도

 

우선 분할을 할 때 N개를 1개씩 남을 때까지 반으로 나눠야하므로 logN의 비용이 들겠죠?

 

그리고 합쳐지는 과정에서 모든 숫자를 비교하여 더 작은 숫자로 합치기 때문에 N번의 비용이 듭니다.

 

고로 시간복잡도는 N * logN 즉, NlogN 입니다.

---

코드 구현

 

이제 이론을 이해했으니 코드로 직접 구현해봐야겠죠?

 

정렬되지 않은 숫자들이 담긴 numbers를 만들어줍니다.

 

var numbers:[Int] = [4,1,7,5,3,2,6]

 

이제 이 numbers를 반으로 나누어줘야겠죠?

 

만약 1개보다 적다면 반으로 나눌 수 없으므로 list를 return 해줍니다.

 

2개 이상이라면 left와 right로 반으로 나눠줍니다.

 

그리고 merge를 통해서 나눠진 left와 right를 합쳐준 것을 return 해줍니다.

 

private func divide(_ list:[Element]) -> [Element] {
        if list.count <= 1 { return list }
        let mid:Int = list.count/2
        let left:[Element] = Array(list[0..<mid])
        let right:[Element] = Array(list[mid..<list.count])
        return merge(divide(left), divide(right))
    }

 

왼쪽과 오른쪽의 숫자들을 비교해주면서 더 작은 숫자들로 새로운 list를 만들어줍니다.

 

만약 l이나 r에 남은 숫자들이 있다면 list에 모두 넣어주고 반환해줍니다.

 

private func merge(_ left:[Element],_ right:[Element]) -> [Element] {
        var l:[Element] = left
        var r:[Element] = right
        var list:[Element] = []
        
        while !l.isEmpty && !r.isEmpty {
            if l.first! < r.first! {
                list.append(l.removeFirst())
            }else {
                list.append(r.removeFirst())
            }
        }
        list.append(contentsOf: l+r)
        return list
    }

---

전체 코드