Go 언어로 병합 정렬을 구현하여 분할 정복 기법을 설명하겠습니다. Go는 정적 타입 언어로, 효율적인 메모리 관리와 성능이 특징입니다. 병합 정렬을 통해 분할 정복 알고리즘의 원리를 Go에서 어떻게 구현하는지 살펴보겠습니다.
병합 정렬 (Merge Sort) in Go
병합 정렬은 다음과 같은 단계로 이루어집니다:
- 배열을 반으로 나눕니다.
- 각 하위 배열을 재귀적으로 병합 정렬합니다.
- 정렬된 하위 배열들을 병합하여 최종 정렬된 배열을 만듭니다.
다음은 병합 정렬의 Go 구현 예제입니다:
go
코드 복사
package main import ( "fmt" ) func mergeSort(arr []int) []int { if len(arr) <= 1 { return arr } mid := len(arr) / 2 left := mergeSort(arr[:mid]) right := mergeSort(arr[mid:]) return merge(left, right) } func merge(left, right []int) []int { sortedArray := make([]int, 0, len(left)+len(right)) i, j := 0, 0 for i < len(left) && j < len(right) { if left[i] < right[j] { sortedArray = append(sortedArray, left[i]) i++ } else { sortedArray = append(sortedArray, right[j]) j++ } } sortedArray = append(sortedArray, left[i:]...) sortedArray = append(sortedArray, right[j:]...) return sortedArray } func main() { unsortedArray := []int{38, 27, 43, 3, 9, 82, 10} sortedArray := mergeSort(unsortedArray) fmt.Println("정렬된 배열:", sortedArray) }
설명
- mergeSort 함수:
- 배열의 길이가 1 이하인 경우, 이미 정렬된 상태이므로 그대로 반환합니다.
- 배열을 두 개의 하위 배열로 나눕니다.
- 두 하위 배열을 재귀적으로 정렬합니다.
- merge 함수를 사용하여 두 정렬된 하위 배열을 병합합니다.
- merge 함수:
- 두 정렬된 배열을 병합하여 하나의 정렬된 배열을 만듭니다.
- 각 배열의 요소들을 비교하면서 작은 요소를 결과 배열에 추가합니다.
- 한쪽 배열의 요소가 모두 소진되면, 나머지 배열의 요소들을 결과 배열에 추가합니다.
병합 정렬은 시간 복잡도가 O(n log n)으로, 안정적인 정렬 알고리즘입니다. 이 예제는 분할 정복의 원리를 Go 언어로 어떻게 구현