MergeSort (with Swift)

 Merge Sort

큰 덩어리를 작게 나누고, 나뉘어진 것들을 sorting 한 후 합치면서 정렬하는 방법을 Merge Sort 라고 합니다. 

 

예를 들어 10개의 elements 가 있는 경우, 해당 array 를 sorting 하려면 위에서 썼던 방법들을 사용했을 때 O(n^2), 약 100 번의 과정이 소요된다고 가정해볼게요.

 

만약 array 를 반으로 나눈 후 sorting, 합칠때 다시 sorting 해주면 과정이 많이 줄어들 수 있습니다. 위와 같은 방식으로 한다면 5^2 이 두번, 그리고 합치는 경우에는 모든 element 들을 한번씩 비교하고 배치해야하니 10번 으로 잡으면 (25 + 25 + 10 ) 60번 이네요. 

 

그런데말입니다, 이러한 과정을 끝없이 (각 element 가 하나가 될 때까지) 하면 어떻게 될까요 ?? 

우선 과정을 big O 표기법으로 정리해보면 다음과 같습니다.

 

1. n 개의 elements 를 가진 1개의 array -> 1 개의 element 를 가진 n 개의 array      O(n)

2 개 -> 1회

4 개 -> 3회

8 개 -> 7회

16 개 -> 15회

...

 

 

2. 비교, 정렬 (16개 element 로 가정)

1 x 16개 2개씩 짝지어 비교 -> 16 회

2 x 8 개 2개씩 짝지어 비교 -> 16 회

4 x 4 개 2개씩 짝지어 비교 -> 16 회

8 x 2 개 2개씩 짝지어 비교 -> 16 회

16 x 1 개 2개씩 짝지어 비교 -> 16 회

 

정리

1. 과정은 n 개의 elements 일 때 나누는 데 총 n 번이 필요합니다. ( O(n))

2. 과정은 n 회의 비교과정이 log n 번 만큼 일어나므로 총 n * log n 번이 필요합니다. (O(n log n))

따라서, mergeSort 은 O(n log n) 의 Time Complexity 를 갖습니다.

 

 

 

 

 

 

예시를 통해 과정을 설명해드릴게요 ! 

0.  8 개의 element 가 array 에 있다고 가정해볼게요.

[6, 5, 3, 1, 8, 7, 2, 4]

1. 이 elements 반으로 나눕니다. 나눈 후 정렬하면 더 빠르게 할 수 있으니까요.

[6, 5, 3, 1], [8, 7, 2, 4]

2. 더더 빠르게 하기 위해서 또다시 나눕니다.

[6, 5], [3, 1], [8, 7], [2, 4]

3. 더더더 빠르게 하기 위해서 다시 한번 나눕니다.

 

[6], [5], [3], [1], [8], [7], [2], [4]

4. 이제 나눌수가 없습니다. 지금부터 합치면서 정렬을 시작하겠습니다.

 

5. 각 상자에 있는 element 를 앞에서부터 2개씩, 보고 비교해서 작은 값을 앞에, 큰 값을 뒤에 둡니다. (2개 들어있는 상자 4 생성 )

// [6], [5],    [3], [1],    [8], [7],    [2], [4]

[5, 6],         [1, 3],       [7, 8],      [2, 4]

6. 2개의 상자들 (2개의 elements 가 들어있는) 에서 각각의 element 들을 비교 후, 4 * 1 상자에 넣습니다. (4개 들어있는 상자 2 생성)

// [5, 6], [1, 3],          [7, 8], [2, 4]

[1, 3, 5, 6],                [2, 4, 7, 8]

7. 위 과정을 반복합니다. (8 * 1 의 상자가 생겼고, 정렬이 완료되었습니다.) 

 

 

 

 

 

5, 6, 7 과정을 사실 똑같아요. 과정이 많이 축약되어 있는 것 같아 과정에 대해 추가로 설명드리겠습니다.

// [5, 6], [1, 3], [7, 8], [2, 4]

 [5,6] ~ [1, 3] 비교
1.   5 와 1 비교 ->  1 이 더 작으므로 1을 우선 배치  [1]
2.   5 와 3 비교 ->  3 이 더 작으므로 3을 그 후에 배치 [1, 3]
3.   5, 6 비교할 대상 없으므로 그 뒤에 배치 [1, 3, 5, 6]

[7,8], [2,4] 비교
1.   7 와 2 비교 ->  2 이 더 작으므로 2을 우선 배치  [2]
2.   7 와 4 비교 ->  4 이 더 작으므로 4을 그 후에 배치 [2, 4]
3.   7, 8 비교할 대상 없으므로 그 뒤에 배치 [2, 4, 7, 8]

[1, 3, 5, 6], [2, 4, 7, 8]

 

 

다음으로, Swift 로 구현한 MergeSort 입니다. 

func mergeSort1(_ array:[Int]) -> [Int]{

    if array.count > 1 {   // if array has more than 1 element, divide it.
        var firstHalfArray = [Int]()  // initiate empty Int array
        var lastHalfArray = [Int]()
        
        let half = array.count / 2

        for i in 0 ..< array.count {
            if i < half { // first half of array is going to be 'firstHalfArray'
                firstHalfArray.append(array[i])
            } else {      // last half of array
                lastHalfArray.append(array[i])
            }
        }
        return merge(mergeSort1(firstHalfArray), mergeSort1(lastHalfArray))
    } // if it has a only element, return self 
    return array
}

 

 

 

func merge(_ array1: [Int], _ array2: [Int]) -> [Int] { // merge only sorted!! array

    var resultArray = [Int]()
    var array1Index = 0
    var array2Index = 0

    while (array1.count > array1Index || array2.count > array2Index) {
    
        // validity check for both array1 and array2
        
        // if one of arrayIndexes is equal to the number of array it's using for,
        //  append the other array to the end of resultArray. then, return!
        
        if array1Index == array1.count {
            // need to merge remained arrays , not the whole part.
            for index2 in array2Index ..< array2.count {
                resultArray.append(array2[index2])
            }
            break
        }
        
        if array2Index == array2.count {
            for index1 in array1Index ..< array1.count {
                resultArray.append(array1[index1])
            }
            break
        }
        
        // compare elements one by one. If one(a) is smaller than or equal to the other(b), 
        //put first one(a) at the end of resultArray, and add 1 to the index of that array

	if array1[array1Index] <= array2[array2Index] {
            resultArray.append(array1[array1Index])
            array1Index += 1
        } else {
            resultArray.append(array2[array2Index])
            array2Index += 1
        }
    }

    return resultArray
}

mergeSort 를 위와 같이 두개의 function 을 이용하여 구현하였습니다. 

 

첫번째 함수 mergeSort1(_) 은 하나의 array 를 반으로 나누고, 나누어진 배열을 'return merge(mergeSort1(_), mergeSort2(_))' 

안에 넣어줍니다. (Recursion) 

단, element 가 하나일 때는 element를 반환합니다. (terminating condition for recursion)

 

merge 함수는 이미 정렬된 두 array 들만 정렬할 수 있는 함수이고, 실제로 merge 함수에는 이미 정렬된 array 만 parameter 로 들어오게 됩니다. 

 

예를들어  [4,3,2,1] 을 mergeSort1 을 이용한다고 했을 때 흐름은 아래와 같습니다.

mergeSort1(_:) input:[4, 3, 2, 1]
mergeSort1(_:) input:[4, 3]  // first part of merge(mergeSort[4,3], [2,1])begin
mergeSort1(_:) input:[4]
mergeSort1(_:) input:[3]
merge(_:_:)    input:[4], [3] // first part ended

mergeSort1(_:) input:[2, 1]   // second part of merge(mergeSort[4,3], [2,1]) begin
mergeSort1(_:) input:[2]
mergeSort1(_:) input:[1]
merge(_:_:)    input:[2], [1] // second part ended

merge(_:_:)    input:[3, 4], [1, 2]

 

merge 함수에서 전체적인 과정은 다음과 같습니다. 

1. 각 sorted 된 array 에서 가장 앞에 있는 element 두개 (a,b) 를 비교 후, 더 작거나 같으면 그 element (a)를 result Array 에 넣고, 사용된 array 내 다음 element (a' ~ b)와 다시 비교합니다. 해당 과정을 하나의 행렬의 마지막 element 가 사용될 때까지 반복합니다.

 

2. 하나의 행렬이 모두 사용되었으면, result Array 에 나머지 행렬 중 사용되지 않은 부분을 마지막에 붙입니다. 

(코드에서 해당 부분 순서는 바뀌었습니다.)

 

 

수고 많으셨습니다. Quick Sort 와 MergeSort 는 Sorting 에서 많이 쓰이는 Algorithm 이므로 꼭 알아가시면 좋을 것 같습니다. 다음으로는 Quick Sort 에 대해 포스팅하도록 하겠습니다. 

 

Generic 을 사용했을 때 각 function type 에 대해 적는 것을 끝으로 글을 마치겠습니다. 긴 글 읽어주셔서 감사합니다 

func mergeSort1 <T: Comparable>(_ array:[T]) -> [T]
func merge <T: Comparable> (_ array1: [T], _ array2: [T]) -> [T]

정말 마지막으로, merge 에서 각 element 를 비교해야 하기 때문에 T 는 Comparable protocol 을 Conform 해야 합니다.

 

그리고, Swift - Core Library - Darwin 에 이미 mergesort 가 있기때문에 mergeSort1 로 이름 지은 점 참고해주세요.

(물론 parameter, return type, 함수 이름 (s, S) 이 모두 다르기때문에 다른 function 이지만요.. )