Swift) 분할 정복 :: 합병 정렬(Merge Sort) 구현 해보기

 

 

 

안녕하세요!!!!!!!!!!!!!!!! 소들입니다 :)

오늘의 마지막 포스팅은 분할 정복 중에서도~~ 합병 정렬~~

아마 합병 정렬까지 공부하면, 모든 정렬에 대해 다뤘다고 봐도 될 거 같아요 :)

아, 혹시 분할 정복과 퀵 정렬에 대해 모른다면 이 포스팅을 보고 오시길!!!

 

음.. 근데 제가 생각하기엔

정렬 중에서 가장? 난이도가 있다고 생각 돼요!!! 😱

이해하기가 좀 어려울 수 있으니 꼭 코드를 직접 짜보시는 걸 추천합니다~~

 모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 합병 정렬이 모야?

 

합병 정렬 또한, 분할 정복 알고리즘 중 하나로,

퀵 정렬과 마찬가지로 재귀 함수를 이용함!!! 어떤 로직으로 동작하냐면,

 

 

① 배열을 절반으로 잘라, 두 배열로 나눔

(배열의 갯수가 7같이 홀수일 경우, 3개&4개로 나눔)

②  배열의 갯수가 1개 이하일 때까지 위 작업을 재귀함수로 반복함

③ 재귀 함수는 나눠진 두 배열을 합병 정렬을 이용해 정렬하고 리턴함

 

 

오... 합병 정렬이 뭔지 설명하는데 합병 정렬 하라고 나오는 건 무슨 경우ㅎ;;

자 먼저, 위에서 나눠진 두 배열을 합병 정렬한다는 것은,

 

 

 

 

위 그림처럼 두 배열을 0번 index부터 비교하며,

작은 값부터 나열하는 것을 합병 정렬이라고 함

 

왼쪽 배열의 0번 Index가 작으면 왼쪽 배열의 0번 index를 나열하고,

이제 왼쪽 배열의 1번 index와 오른쪽 배열의 0번 index를 비교하는 것임

이런 식으로 두 배열의 전체 값을 정렬하는 것이 합병 정렬!

 

근데 합병 정렬은 위 과정을,

배열의 갯수가 1개 이하(재귀 탈출 조건)이 될 때까지 재귀로 호출하여

배열을 반으로 쪼갠 다음에, 재귀를 탈출하면,

쪼개진 두 배열을 합병 정렬하여 리턴함!

 

 

흐..움..

이론이 조금 어려울 수 있기에 전체 과정을

위키피디아에서 이해하기 쉬운 짤을 들고왔음

 

 

출처 : 위키피디아

 

 

이론은 이제 이해가 됐길..:)

그럼 코드로 구현해보자

 

 

 

 

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))
}

 

 

합병 정렬하는 함수가 별도로 필요해서

따로 선언을 해줘서 만들어주어야 함!! :) 

차근차근 읽으면 어렵지 않아요 🌝

 

 

 

 

 

4. 합병 정렬의 시간 복잡도

 

합병 정렬의 시간 복잡도는 

 

O(n log n)

 

으로, 퀵 정렬과 같음 :)

고로, 분할 정복 알고리즘인 퀵 정렬과 합병 정렬이

버블&선택&삽입 정렬보다 성능이 훨 좋다~

 

 

 

 

 

 

 

.

.

.

드디어 정렬 알고리즘 끝 :)

피드백, 궁금점은 언제든 댓글 남겨 주세요~~