합병정렬, 힙정렬, 기수정렬

Groot·2022년 12월 12일

TIL 알고리즘

TIL

목록 보기

108/153

TIL

🌱 난 오늘 무엇을 공부했을까?

📌 알고리즘 스터디 - 정렬 알고리즘

📍 합병정렬

비교 기반 정렬 알고리즘.
수열을 하나의 수가 될 때까지 분할을 한 후 다시 병합하는 정렬 방식이다.

🔗 구현방법

리스트의 길이가 1 이하라면 이미 정렬된 것으로 본다.
분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. <- 실제 정렬이 이뤄지는 구간.
복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

🔗 장단점

장점
- input의 정렬 정도에 관련없이 어느 정도의 성능을 보장해준다.
단점
- 이미 정렬되어 있는 Input이라도 항상 같은 횟수의 연산을 한다.
- 별도의 임시 배열이 필요하다.(제자리 정렬 = in-place sorting)이 아니다.
- 추가적인 Memory가 필요하다.

🔗 시간복잡도

최악 시간복잡도 O(n log n)
최선 시간복잡도 O(n log n)
평균 시간복잡도 일반적으로, O(n log n)
공간복잡도 О(n)

🔗 코드

import Foundation

func mergeSort(_ value: [Int]) -> [Int] {
    guard value.count > 1 else { return value }
    
    let mid = value.count / 2
    let left = Array(value[0..<mid])
    let right = Array(value[mid..<value.count])
    
    return merge(mergeSort(left), mergeSort(right))
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var left = left
    var right = right
    var result = [Int]()
    
    while !left.isEmpty && !right.isEmpty { // 둘 다 숫자를 가지고 있을 때
        if left.first! < right.first! { // 더 작은 값을 순서대로 넣어준다.
            result.append(left.removeFirst())
        }else {
            result.append(right.removeFirst())
        }
    }
    
    result.append(contentsOf: left+right) // 남은 숫자들을 추가해준다.
    
    return result
}

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
https://babbab2.tistory.com/102

📍 힙정렬

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

🔗 구현방법

정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
- 내림차순을 기준으로 정렬
현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
힙의 사이즈가 1보다 크면 위 과정 반복

루트를 마지막 노드로 대체 (11 → 4), 다시 최대 힙 구성

🔗 장단점

장점
- 최악의 경우에도 시간 복잡도인 θ(nlogn)을 보장한다.
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라, 가장 큰 값 몇개만 필요할 때이다.
단점
- 데이터들의 상태에 따라 다른 정렬법들에 비해서 조금 느린편이다.
- 데이터의 순서가 바뀌는 unstable한 알고리즘이다.

🔗 시간복잡도

최악 시간복잡도 O(n log n)
최선 시간복잡도 O(n log n)
평균 시간복잡도 일반적으로, O(n log n)
공간복잡도 О(1)

🔗 코드

func heapSort(_ value: [Int]) -> [Int] {
    var result = value
    
    for index in stride(from: result.count - 1, through: 0, by: -1) { // MaxHeap을 구성하기 위해서 루트(0) 값이 가장 커야하기 때문에 배열의 뒤에서(heap의 가장 아래부분)부터 반복시작
        result = makeMaxHeap(result, index) // MaxHeap을 만들어줌
        result.swapAt(0, index) // root 값이 가장 커야하기 때문에 가장 큰 값을 root로 이동
    }
    
    return result
}

func makeMaxHeap(_ value: [Int], _ maxIndex: Int) -> [Int] {
    var result = value
    
    for index in stride(from: maxIndex, to: 0, by: -1) { // 마찬가지로 밑에서부터 부모의 값보다 자식의 값이 크면 변경
            if result[index] > result[index/2] {
                result.swapAt(index, index/2)
            }
        }
    
    return result
}

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
https://sweetlog.netlify.app/algorithm/heap_sort/

📍 기수정렬

기수 별로 비교 없이 수행하는 정렬 알고리즘이다

🔗 구현방법

0~9 까지의 Bucket(Queue 자료구조의)을 준비한다.
모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.
0부터 차례대로 버킷에서 데이터를 다시 가져온다.
가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.

예시

1의 자리 숫자부터 bucket의 자릿수로 할당.
- 예) 15는 1의 자리가 5라서 Queue에 할당.

0번 bucket 부터 꺼내온다.
- 1의 자릿수로 정렬된 숫자들.

다시 10의 자리도 마찬가지로 할당.
- 정렬해야 하는 숫자들의 최대 자릿수를 알고 있어야 한다.

동일하게 0번 bucket 부터 꺼내오면 정렬완료

🔗 장단점

장점
- 문자열, 정수 정렬 가능
단점
- 자릿수가 없는 것은 정렬할 수 없음. (부동 소숫점)
- 중간 결과를 저장할 bucket 공간이 필요함.

🔗 시간복잡도

시간 복잡도 : O(d * (n + b))
-> d는 정렬할 숫자의 자릿수, b는 10 (k와 같으나 10으로 고정되어 있다.)
( Counting Sort의 경우 : O(n + k) 로 배열의 최댓값 k에 영향을 받음 )

🔗 코드

func radixSort(_ value: [Int]) -> [Int] {
    let radix = 10 // 0...9까지 숫자를 의미
    var done = false // 언제까지 반복할 지(최대 자릿수)
    var digits = 1 // 1의 자리 
    var result = value 
    
    while !done { 
        done = true // 첫 반복부터 완료가 됬다고 해주고, 내부에 존재하는 반복문에서 값을 변경
        var buckets: [[Int]] = Array(repeating: [], count: radix) // 각 자릿수를 담을 버켓
        
        for number in result { 
            let remainingPart = number / digits // 1의 자리 , 10의 자리 ...
            let digit = remainingPart % radix // 각 자릿수의 index에 넣어주기 위해 나머지를 구한다.
            buckets[digit].append(number) // 각 자릿수에 맞게 수를 할당
            
            if remainingPart > 0 { // remainingPart이 모두 0이면 그 자릿수의 수가 없다고 판단 -> 정렬완료(반복문 종료)
              done = false
            }
        }

        digits *= radix // 다음 자릿수를 비교하기 위함
        result = buckets.flatMap { $0 } // 버켓에 있는 수를 정렬해서 결과에 넣어줌
    }
    
    return result
}