Algorithm - 삽입 정렬 & 기수 정렬

안녕하세요~ Diana 입니다.

오늘은 저희 동네에 역대급으로 많은 눈이 내렸습니다.

어제까지 해서 최고 적설양이 43cm 라고 하더라구요.

처음엔 mm를 잘못 표기한 줄 알았는데 출근하려고 집을 나서는 순간 무너져 있는 지하 주차장 케노피를 보고 사실임을 깨달았습니다.

그자리에서 바로 휴가 쓰고 오늘은 정말 오랫만에 카페에 나와있네요.

 

다친 사람은 없어서 다행입니닷

 

개인적인 이야기는 각설하고 오늘은 삽입 정렬과 기수 정렬에 대해 알아보려고 합니다.

시작할게요!

 

 

---

 

 

✅ 1. 삽입 정렬(Insertion Sort)

삽입정렬은 앞의 원소들이 전부 정렬 되어있다는 가정 하에 현재 원소의 위치를 찾아가는 정렬 방법입니다.

 

 

 

예를 들면 위와 같은 원소들이 있다고 해봅시다.

현재 위치를 찾고자 하는 원소는 7 이며 7 앞의 2, 3, 8, 9 는 이미 정렬이 된 상태라고 가정합니다.

따라서 7은 본인의 위치를 찾아가기 위해 바로 앞의 9 부터 크기를 비교하며 정렬을 위해서 한칸씩 앞으로 전진하게 됩니다.

 

 

삽입 정렬의 시간 복잡도는 1 + 2 + 3 + ... + (N - 1) 로 N(N-1) / 2, 즉 O(N^2) 입니다.

 

삽입 정렬을 Swift 코드로 나타내면 아래와 같습니다.

 

func insertionSort() {
    var array = readLine()!.split(separator: " ").map{ Int($0)! }
    
    for i in 1 ..< array.count {
        var j = i - 1
        while j >= 0 {
            if array[j] > array[j + 1] {
                let temp = array[j + 1]
                array[j + 1] = array[j]
                array[j] = temp
            }
            j -= 1
        }
    }
    
    array.forEach { item in print(item, terminator: " ")}
}

 

 

✅ 2. 기수 정렬

기수 정렬은 다른 정렬들과 조금 다른 특성을 가지고 있습니다.

앞 뒤 원소들과 정렬하고자 하는 원소를 비교하던 앞의 정렬 방법 들과는 다르게 기수 정렬은 자릿 수를 기준으로 원소 들을 정렬합니다.

 

예를 들어 329, 457, 657, 839, 436, 720, 355 를 비교한다고 가정하겠습니다.

기수 정렬은 우선 0부터 9까지의 숫자가 담긴 배열을 준비합니다.

그리고 각 원소들을 자릿수 별로 분리한 뒤 첫번째 자리수인 3, 4, 6, 8, 4, 7 ,3 만을 비교하여 원소들을 정렬합니다.

 

처음 정렬이 이루어지면 결과는 [329, 355, 457, 436,, 647, 720, 839]로 과정은 아래와 같습니다.

 

 

이렇게 정렬된 배열은 다음 자리수를 기준으로 동일하게 정렬이 이루어집니다.

그리고 마지막 자릿수를 기준으로 한 정렬이 완료되었을 때 비로소 결과 값을 얻을 수 있습니다.

여기서 주의해야할 점은 만약 각 원소들의 자릿수가 달라 비교하려는 자릿수가 없는 경우 해당 값은 0으로 간주되어 배열의 맨 앞에 정렬됩니다.

 

기수 정렬의 시간 복잡도는 원소들 중 max 값의 자릿수 k, 그리고 N개의 원소를 비교하므로 O(kN), 즉 O(N)이 됩니다.

 

 

기수 정렬을 Swift 코드로 나타내면 아래와 같습니다.

 

func radixSort() {
    let input = Int(readLine()!)! // CodeTree 요구사항
    var array = readLine()!.split(separator: " ").map{ Int($0)! }
    let maxLength = String(array.max()!).count
    
    var sortArray = [[Int]]()
    
    for index in 0 ..< maxLength {
        sortArray = [[Int]](repeating: [], count: 10)
        
        for item in array {
            if item.split().count < index + 1 {
                sortArray[0].append(item)
                return
            }
            
            let indexNum = item.split()[index]
            sortArray[indexNum].append(item)
            
            array = sortArray.flatMap { $0 }
        }
    }
    
    sortArray.forEach { items in
        items.forEach { item in
            print(item, terminator: " ")
        }
    }
}

extension Int {
    func split() -> [Int] {
        var array: [Int] = []
        
        for char in String(self) {
            array.append(Int(String(char))!)
        }
        
        return array
    }
}

 

이렇게 오늘은 삽입정렬과 기수 정렬에 대해 알아보았습니다.