스위프트 코딩테스트 강좌, 병합 정렬

안녕하세요. 오늘은 스위프트로 구현하는 병합 정렬(Merge Sort) 알고리즘에 대해 알아보겠습니다. 이 강좌에서는 병합 정렬의 기초부터 시작하여, 실제 코딩 테스트에서의 활용 방법까지 자세히 설명하겠습니다.

병합 정렬이란?

병합 정렬은 분할 정복(divide and conquer) 전략에 기반한 정렬 알고리즘입니다. 이 알고리즘은 배열을 반으로 나누고, 각 서브배열을 정렬한 다음, 두 개의 정렬된 서브배열을 하나의 정렬된 배열로 병합합니다. 병합 정렬은 평균과 최악의 경우 시간 복잡도가 O(n log n)이며, 안정 정렬(stable sort)입니다.

병합 정렬의 원리

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

원본 배열이 주어지면, 해당 배열을 중간 지점에서 두 개의 서브배열로 분할합니다.
각 서브배열에 대해 재귀적으로 병합 정렬을 수행합니다.
정렬된 두 서브배열을 병합하여 하나의 정렬된 배열을 생성합니다.

이여기서 중요한 점은, 각 단계에서 서브배열이 정렬되어 있다는 점입니다. 이 정렬된 배열을 다시 함께 합치는 방식으로 전체 배열을 정렬하게 됩니다.

문제: 정수를 정렬하라

주어진 정수 리스트를 오름차순으로 정렬하는 함수를 스위프트로 작성하시오. 입력 예시는 다음과 같습니다:


            let nums = [38, 27, 43, 3, 9, 82, 10]

이 문제를 풀기 위해서는 위에서 설명한 병합 정렬의 원리를 적용하여야 합니다.

병합 정렬 구현하기

이제 스위프트 코드로 병합 정렬을 구현해 보겠습니다. 아래는 전체적인 코드 입니다:


            func mergeSort(_ array: [Int]) -> [Int] {
                // 1. 배열의 크기가 1보다 작으면 원본 배열 반환
                if array.count < 2 {
                    return array
                }
                
                // 2. 배열을 중간 지점에서 분할
                let midIndex = array.count / 2
                let leftArray = mergeSort(Array(array[0.. [Int] {
                var mergedArray: [Int] = []
                var leftIndex = 0
                var rightIndex = 0
                
                // 4. 두 배열을 비교하며 병합
                while leftIndex < left.count && rightIndex < right.count {
                    if left[leftIndex] < right[rightIndex] {
                        mergedArray.append(left[leftIndex])
                        leftIndex += 1
                    } else {
                        mergedArray.append(right[rightIndex])
                        rightIndex += 1
                    }
                }
                
                // 5. 남은 요소들 추가
                while leftIndex < left.count {
                    mergedArray.append(left[leftIndex])
                    leftIndex += 1
                }
                
                while rightIndex < right.count {
                    mergedArray.append(right[rightIndex])
                    rightIndex += 1
                }
                
                return mergedArray
            }

            // Main
            let nums = [38, 27, 43, 3, 9, 82, 10]
            let sortedNums = mergeSort(nums)
            print(sortedNums) // 결과: [3, 9, 10, 27, 38, 43, 82]

위 코드는 입력된 숫자 리스트를 병합 정렬을 통해 정렬한 후, 결과를 출력합니다. 각 단계별로 주석을 달아 이해를 돕고 있습니다.

코드 설명

코드를 한 줄씩 살펴보겠습니다:

if array.count < 2 { return array }: 배열의 크기가 1보다 작다면 이미 정렬된 상태이므로 그대로 반환합니다.
let midIndex = array.count / 2: 배열의 중간 인덱스를 계산합니다.
let leftArray = mergeSort(Array(array[0..: 왼쪽 서브배열을 재귀적으로 정렬합니다.
let rightArray = mergeSort(Array(array[midIndex..: 오른쪽 서브배열도 마찬가지로 정렬합니다.
return merge(leftArray, rightArray): 정렬된 왼쪽과 오른쪽 배열을 병합하여 결과를 반환합니다.

병합 함수에서는 인덱스를 추적하면서 두 배열을 각각 비교해가며 병합합니다. 만약 하나의 배열이 끝나면 나머지 요소들을 추가하여 최종 결과를 생성합니다.

병합 정렬의 장점과 단점

병합 정렬은 다음과 같은 장점과 단점이 있습니다:

장점:

안정적인 정렬: 동일한 값을 가진 요소들의 상대적인 순서가 보존됩니다.
시간 복잡도가 O(n log n): 데이터 양에 비례하여 비교적 빠른 정렬 성능을 보입니다.
크기가 고정된 배열이 아닌 Linked List에도 적용 가능: 포인터를 이용한 구조체에서도 사용 가능합니다.

단점:

추가적인 메모리가 필요: 병합 과정에서 새로운 배열을 생성하기 때문에 공간 복잡도가 O(n)입니다.
간단한 경우(예: 거의 정렬된 경우)에서는 삽입 정렬 같은 간단한 알고리즘이 오히려 성능이 좋을 수 있습니다.

실력 향상을 위한 추가 문제

병합 정렬을 이해했으니, 추가 문제를 통해 더 연습해보세요:

정수 배열이 주어졌을 때, 중복된 숫자를 제거한 정렬된 배열을 반환하는 함수를 작성하시오.
배열이 정렬되어 있을 때, 특정 값을 갖는 요소의 인덱스를 이진 탐색(Binary Search)을 통해 찾는 알고리즘을 구현하시오.
입력으로 들어온 여러 배열을 병합하여 하나의 정렬된 배열로 만드는 함수를 스위프트로 작성하시오.