[Swift] - Merge Sort(병합정렬) + 백준 24060

병합 정렬 은근 어렵더라구용 헤헤
Swift로 된 풀이도 많이 없구 😰
그래서 포스트로 정리해보려합니당

Merge Sort 란?

분할 정복 알고리즘의 하나로,
배열을 두 개로 분할 하여 정렬한 후 이를 합치는 알고리즘이다.

그래서 병합정렬 알고리즘의 프로세스는

• 분할 : 주어진 배열을 둘로 나눔
• 정복 : 나눠진 배열을 정렬
• 결합 : 정렬된 배열을 합침

으로 진행된다.
이때 정복하는 과정에서 나눠진 배열이 충분히 작지 않은 경우 또다시 분할, 정복 과정을 진행하게 되는데 이는 재귀함수로 구현한다.

Merge Sort 프로세스

병합정렬의 프로세스를 이미지로 보면 다음과 같다

1. 주어진 배열을 분할한다
   • [38, 17, 43, 3, 9, 82, 10]
2. 각 배열에 하나의 원소만 남을때까지 계속해서 분할한다
   • [38]과 [27]
3. 분할이 끝나면 배열 내 원소들의 크기를 비교하여 배열을 결합한다.
   • [27, 38]

이 과정을 여기 에서 더 자세히 볼 수 있다.

Swift로 작성하는 Merge Sort

var numArray = [Int]()

• 정렬하려는 배열

func mergeSort(_ array: [Int], _ start: Int, _ end: Int) {
	if array.count <= 1 { return }
    
	if start < end {
    	let center = (start + end) / 2
    	mergeSort(array, start, center)
        mergeSort(array, center + 1, end)
        merge(start, center, end)
    }
}

• 분할, 정복

func merge(_ start: Int, _ center: Int, _ end: Int) {
	var i = start
    var j = center + 1
    var t = 0
    var sortedArray = [Int]()
    
    while i <= center && j <= end {
    	if numArray[i] <= numArray[j] {
        	sortedArray.append(numArray[i]
            i += 1
        } else {
        	sortedArray.append(numArray[j]
            j += 1
        }
    }
    
    while i <= center {
    	sortedArray.append(numArray[i])
        i += 1
    }
    
    while j <= end {
    	sortedArray.append(numArray[j]
        j += 1
    }
    
    i = start
    
    while i <= end {
    	numArray[i] = sortedArray[t]
        i += 1
        t += 1
    }
}

• 병합

- 백준 24060 알고리즘 수업 - 병합 정렬 1 풀이

let input = readLine()!.split(separator:" ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var numArray = readLine()!.split(separator:" ").map{Int(String($0))!}
var count = 0
var answer = -1

func mergeSort(_ array: [Int], _ start: Int, _ end: Int) {
    if array.count <= 1 { return }
    if start < end && count < K {
        let center = (start + end) / 2
        mergeSort(array, start, center)
        mergeSort(array, center + 1, end)
        merge(start, center, end)
    }
}

func merge(_ start: Int, _ center: Int, _ end: Int) {
    var i = start
    var j = center + 1
    var t = 0
    var temp = [Int]()
    
    while i <= center && j <= end {
        if numArray[i] <= numArray[j] {
            temp.append(numArray[i])
            i += 1
        } else {
            temp.append(numArray[j])
            j += 1
        }
    }
    
    while i <= center {
        temp.append(numArray[i])
        i += 1
    }
    
    while j <= end {
        temp.append(numArray[j])
        j += 1
    }
    
    i = start
    while i <= end {
        numArray[i] = temp[t]
        count += 1
        if count == K {
            answer = temp[t]
            break
        }
        i += 1
        t += 1
    }
}

mergeSort(numArray, 0, N - 1)
print(answer)

참고

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
https://algorithm-visualizer.org/divide-and-conquer/merge-sort