Swift로 정렬 알고리즘 정리하기 ... 2

 

안녕하세요. 린다입니다.

오늘은 정렬 두번째.. 병합(분할)정렬과 기수 정렬에 대해서 정리해볼게요!

 

병합 정렬

• 데이터를 분할하고, 분할한 집합을 정렬하며 합치는 알고리즘
• O(nlogn)의 시간 복잡도) N번의 데이터 접근이 logN 번 일어남
• 경주 문제에서 활용됨
• 하나의 배열을 가장 작은 크기까지 분할한 다음 2개의 포인터를 가지고
  각 포인터 값의 비교를 통하여 정렬 후 합치고를 반복하는 기법

Two Pointer를 활용한 코드

// MARK: - 병합 정렬
func mergeSort(_ array: inout [Int], _ left: Int, _ right: Int) -> [Int] {
    if (left < right) {
        let m = left + (right - left) / 2 // overflow 방지
        
        mergeSort(&array, left, m)
        mergeSort(&array, m+1, right)
        merge(&array, left, right, m)
    }
    
    return array
}

func merge(_ array: inout [Int], _ left: Int, _ right: Int, _ m: Int) {
    var temp = [Int]()
    var leftPointer = left
    var rightPointer = m + 1
    var k = 0
    
    while (leftPointer <= m && rightPointer <= right) {
        if array[leftPointer] <= array[rightPointer] {
            temp.append(array[leftPointer])
            leftPointer += 1
        } else {
            temp.append(array[rightPointer])
            rightPointer += 1
        }
    }
    
    // 오른쪽 배열이 정렬이 다 되고 왼쪽 배열에 값이 남아 있다면
    while(leftPointer <= m) { // == leftPointer <= left.count
        temp.append(array[leftPointer])
        leftPointer += 1
    }
    
    while(rightPointer <= right) {
        temp.append(array[rightPointer])
        rightPointer += 1
    }
    
    for i in 0..<temp.count {
        array[left + i] = temp[i]
    }
}

var arr = [29, 3, 2, 1, 0]
print(mergeSort(&arr, 0, arr.count - 1))

 

 

 

기수 정렬

• 값이 아니라 요소의 자릿수를 비교해서 정렬하는 기법
• 1의 자리 → 10의 자리 → 100의 자리 … (max숫자의 자리수)까지 queue를 사용하여 정렬
• 각 자리수 별로 0~9가 올 수 있기 때문에 10개의 큐를 사용함
• 시간복잡도 O(kn) / k : 데이터의 자릿수

// 최대 자릿수 찾기
func getMax(_ array: [Int]) -> Int {
    guard let maxCount = array.max() else { return 0 }
    return maxCount
}

// 기수 정렬
func radixSort(_ array: inout [Int]) {
    let maxElement = getMax(array)
    var exp = 1 // 현재 뽑아낼 자릿수를 의미함 ( 1의 자리 -> 10의 자리 -> 100의 자리)
    
    while maxElement / exp > 0 {
        countingSortQueues(&array, exp)
        exp *= 10
    }
}

// 자릿수 비교 함수정렬
func countingSortQueues(_ array: inout [Int], _ exp: Int) {
    var queues: [[Int]] = Array(repeating: [], count: 10)
    
    for num in array {
        let digit = (num / exp) % 10 // 한자리 씩 빼서 확인하기
        queues[digit].append(num)
    }
    
    var index = 0
    for queue in queues {
        for num in queue {
            array[index] = num
            index += 1
        }
    }
}

var arr = [170, 45, 75, 90, 802, 24, 2, 66]
print(radixSort(&arr))