안녕하세요. 오늘은 스위프트로 구현하는 병합 정렬(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)을 통해 찾는 알고리즘을 구현하시오.
- 입력으로 들어온 여러 배열을 병합하여 하나의 정렬된 배열로 만드는 함수를 스위프트로 작성하시오.