[알고리즘] 4강 병합정렬 (merge sort)

4강 합병 정렬(merge sort)

합병 정렬은 다음과 같은 단계를 가진다

• 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복 : 각각의 작은 문제를 순환적으로 해결
• 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

[6, 4, 1, 2, 3, 5, 7, 8] 을 예시로 합병 정렬하면 아래 그림과 같은 단계로 정렬이 진행된다.

1. 1차원 배열을 가장 작은 단위, 즉 1의 단위까지 쪼갠다.
2. 가장 작은 단위로 쪼갠 후 배열의 왼쪽/오른쪽 값을 비교한다.
3. 작은 값을 새 배열에 추가하고, 다음 작은 값을 새 배열에 추가한다.
4. 비교하는 과정하고 추가하는 과정이 종료되는 어느 한쪽 배열에 값은 남게 되는 데 이때 반복문을 이용해 왼쪽 배열부터 새 배열에 모두 추가하고, 오른쪽 배열에 남은 값을 새 배열에 추가하면 정렬이 된다.

    /// 3. merge sort
        func split(data: [Int]) -> [Int] {
            // 데이터 길이가 1이면 바로 리턴
            if data.count == 1 {
                return data
            }

            // 배열을 가장 작은 단위로 쪼개기
            let medium = data.count / 2
            let left: [Int] = split(data: Array(data[0..<medium]))
            let right: [Int] = split(data: Array(data[medium..<data.count]))
            return merge(left: left, right: right)
        }

        func merge(left: [Int], right: [Int]) -> [Int] {
            var result = [Int]()
            var leftPoint = 0
            var rightPoint = 0

            // 왼쪽, 오른쪽 배열의 값을 비교하여 작은 값부터 배열에 추가
            while leftPoint < left.count && rightPoint < right.count {
                if left[leftPoint] <= right[rightPoint] {
                    result.append(left[leftPoint])
                    leftPoint += 1  // 추가 후 인덱스 증가
                } else {
                    result.append(right[rightPoint])
                    rightPoint += 1 // 추가 후 인덱스 증가
                }
            }

            // 왼쪽 배열의 남은 값을 배열에 모두 추가
            while leftPoint < left.count {
                result.append(left[leftPoint])
                leftPoint += 1
            }

            // 오른쪽 배열에 남은 값을 배열에 모두 추가
            while rightPoint < right.count {
                result.append(right[rightPoint])
                rightPoint += 1
            }

            return result
        }

 

예제 코드

devssun/Algorithm-Study