Swift로 적어보는 버블 / 선택 / 병합 정렬

최근 CS 공부를 위해 Boostcourse의 모두를 위한 컴퓨터 과학(CS50) 강의를 수강하고 있습니다. CS를 전혀 몰라도 쉽고 재밌게 들을 수 있는 강의로 저 또한 만족스럽게 듣고 있습니다. 오늘은 정렬 알고리즘의 대표적인 3가지를 간단하게 알아보고, Swift로 직접 구현해 온전히 습득하고자 합니다.

오늘 우리와 함께 할 배열입니다

 

1. 버블 정렬 Bubble Sort

버블 정렬은 가장 직관적인 알고리즘입니다. 쉽게 말해 '두 요소를 비교 후 순서에 맞게 자리를 바꾼다!'의 문장으로 설명할 수 있습니다.

위 단계를 배열의 끝까지 반복하게 됩니다.

배열 끝까지 반복 후에도 정렬이 되지 않았다면, 다시 한번 같은 과정을 반복하는 식으로 알고리즘을 이어나가는 것이 버블 정렬의 기본 개념입니다. 버블 정렬의 상한선은 O(N^2)의 시간복잡도를 가지고 있으며, 하한선의 경우 정렬이 되었는지 확인하는 과정을 통해 Ω(N)으로 최적화가 가능합니다.

 

이를 Swift 코드로 표현하면 다음과 같습니다.

func bubbleSort(from array: inout [Int]) -> [Int] {
    
    // 1. 배열의 크기만큼 돌기 위한 반복문
    for _ in array {
        
        // 2. 위치 변경이 일어났는지 기록하는 플래그 변수
        var isSwap = false
        
        // 3. 두개 값을 비교하기 위한 반복문
        // Range 범위를 조정(..<, -1)해 index out of range 방지
        for j in 0..<array.count-1 {
            
            // 4. 만약 왼쪽 값이 오른쪽 값 보다 크다면
            // 위치 변경 + 기록
            if array[j] > array[j+1] {
                array.swapAt(j, j+1)
                isSwap = true
            }
        }
        
        // 5. 만약 스왑이 일어나지 않았다면 정렬이 완료되었다는 뜻이므로 반복문 종료
        if !isSwap { break }
    }
    
    return array
}

 

2. 선택 정렬 Selection Sort

선택 정렬의 기본 개념은 '배열 안의 가장 작은 수를 찾아 첫 번째 자리와 바꾼다!'로 설명이 가능합니다.(물론 내림차순의 경우 가장 큰 수를 찾아, 마지막 자리와 바꾸는 것입니다)

배열을 탐색 후 가장 작은 숫자가 결정되면, 가장 앞과 자리를 바꿔줍니다.

그리고 다시 같은 과정을 반복하며 정렬을 진행하는 것이 선택 정렬입니다. 주의해야 할 것은 다음 반복에서는 가장 앞자리와 자리를 바꾸는 것이 아닌, 가장 앞자리 바로 뒤와 자리를 바꿔야 합니다. 계속해서 앞으로만 보내면 정렬이 불가능하기 때문입니다.

 

그리고 선택 정렬은 버블 정렬과 다르게 하한선의 시간복잡도를 개선할 수 없습니다. 매 반복마다 선형 탐색으로 정렬을 확인하는 것이 아니라면, 가장 작은 수와 남아있는 수의 관계를 정렬 중에 파악할 수 없기 때문입니다. 결과적으로 선택 정렬의 시간복잡도는 Θ(N^2)로 나타낼 수 있습니다.

 

이를 Swift 코드로 나타내면 다음과 같습니다.

func selectionSort(from array: inout [Int]) -> [Int] {
    
    // 1. 처음으로 시작할 인덱스부터 반복
    for i in 0..<array.count - 1 {
        
        // 2. 가장 작은 수의 인덱스를 저장할 변수
        var smallestIndex = i
        
        // 3. 처음으로 시작할 인덱스 + 1부터 마지막까지 반복
        for j in i+1..<array.count {
            
            // 4. 만약 가장 작았었던 수가 현재 수 보다 크면
            // 가장 작은 수 업데이트
            if array[smallestIndex] > array[j]  {
                smallestIndex = j
            }
        }
        
        // 5. 처음으로 시작할 인덱스 위치와 위치 변경
        array.swapAt(i, smallestIndex)
    }
    
    return array
}

 

3. 병합 정렬 Merge Sort

병합 정렬은 분할 정복 방식을 사용하는 알고리즘으로 '배열을 계속해서 반으로 나눠 정렬 후 다시 합친다!'로 설명이 가능합니다. 버블 정렬과 선택 정렬에 비해 복잡한 방식을 사용하지만, 그만큼 효율적인 정렬 알고리즘으로 널리 알려져 있습니다.(Swift의 `sorted`함수도 병합 정렬과 삽입 정렬을 합쳐 구현한 방식이라고 합니다.)

병합 정렬의 순서를 정리하면, 아래와 같습니다.

1. 배열을 나눌 수 있을 때까지 반으로 나눈다.
2. 나눌 수 없을 때 하나씩 정렬하며 병합한다.
3. 정렬된 배열끼리 다시 정렬하며 병합한다.

병합 정렬의 시간복잡도는 Θ(N log N)입니다. 버블 정렬과 선택 정렬에 비해 빠르게 정렬할 수 있죠. 하지만 배열을 쪼개고 복사할 때마다 메모리 공간을 사용하기 때문에, 공간 복잡도는 상대적으로 높습니다.(하지만 알고리즘의 특성상 공간 복잡도보다는 시간 복잡도를 더 중요하게 생각하기 때문에, 병합 정렬이 더 많이 선택되는 듯합니다.)

 

위의 과정은 재귀 함수로 구현이 가능하고, Swift로 나타내면 다음과 같습니다.

func mergeSort(from array: [Int]) -> [Int] {
    
    // 1. 만약 배열의 크기가 1보다 작거나 같다면 그대로 반환
    if array.count <= 1 { return array }
    
    // 2. 배열을 반으로 나누기 위한 인덱스
    let center = array.count / 2
    
    // 3. 반으로 나눈 후 왼쪽 영역
    let left = Array(array[0..<center])
    
    // 4. 반으로 나눈 후 오른쪽 영역
    let right = Array(array[center..<array.count])
    
    // 5. 재귀함수 호출
    return merge(left: mergeSort(from: left), right: mergeSort(from: right))
}

private func merge(left: [Int], right: [Int]) -> [Int] {
    
    // 1. 인자값 변경을 위한 값 복사
    var left = left
    var right = right
    
    // 2. 최종 결과를 담을 변수
    var result = [Int]()
    
    // 3. 두 배열 모두 하나라도 남아있으면 반복
    while !left.isEmpty && !right.isEmpty {
        
        // 4. 오른쪽이 더 크면 오른쪽 삭제 + 오른쪽 값 결과 배열에 넣기
        //    왼쪽이 더 크면 왼쪽 삭제 + 왼쪽 값 결과 배열에 넣기
        if left[0] < right[0] {
            result.append(left.removeFirst())
        } else {
            result.append(right.removeFirst())
        }
    }
    
    // 5. 한쪽 배열만 남은 상태일 것이므로, 남은 값들 전부 결과 배열에 넣기
    result.append(contentsOf: left)
    result.append(contentsOf: right)
    
    return result
}

 

정리하기

재귀함수의 개념이 조금 어렵긴 하지만 각 정렬 알고리즘의 핵심을 파악할 수 있었습니다. Swift에서는 이미 잘 구현된 `sort`함수를 사용하면 되긴 하지만(TimSort 방식, O(N Log N)) 기본적인 동작 방식을 아는 것은 늘 중요한 듯합니다.