정렬 알고리즘

sewoong·2022년 12월 9일

1. 버블 정렬

func bubbleSort(_ numbers: [Int]) -> [Int] {
    var numbers = numbers
    for i in stride(from: numbers.count -  1, through: 0, by: -1) {
        for j in stride(from: 0, to: i, by: 1) {
            if numbers[j] > numbers[j+1] {
                numbers.swapAt(j, j+1)
            }
        }
    }
    return numbers
}

서로 인접한 두 원소를 검사하여 자리를 바꾸어 정렬하는 방법이다.
시간복잡도는 O(n²)이다.

2. 선택 정렬

func selectionSort(_ numbers: [Int]) -> [Int] {
    var numbers = numbers
    for i in stride(from: 0, to: numbers.count - 1, by: 1) {
        var minIdx = i
        for j in stride(from: i+1, to: numbers.count, by: 1) {
            if numbers[minIdx] > numbers[j] {
                minIdx = j
            }
        }
        numbers.swapAt(i, minIdx)
    }
    return numbers
}

정해진 위치에 알맞은 원소를 넣는 알고리즘이다.
시간복잡도는 O(n²)이다.

3. 삽입 정렬

func insertionSort(_ numbers: [Int]) -> [Int] {
    var numbers = numbers
    
    for i in 1..<numbers.count {
        for j in 0..<i {
            if numbers[i] < numbers[j] {
                let temp = numbers[i]
                numbers.remove(at: i)
                numbers.insert(temp, at: j)
                break
            }
        }
    }
    return numbers
}

정해진 원소를 알맞은 위치에 넣는 알고리즘이다.
시간복잡도는 O(n²)이다.

4. 퀵 정렬

func quickSort(_ numbers: [Int]) -> [Int] {
    if numbers.count <= 1 {
        return numbers
    }
    let pivot = numbers[(numbers.count) / 2]
    let left = numbers.filter { $0 < pivot }
    let right = numbers.filter { $0 > pivot }
    return quickSort(left) + [pivot] + quickSort(right)
}

하나의 pivot(기준)을 고르고, pivot보다 작은 원소들을 왼쪽으로, pivot보다 큰 원소들을 오른쪽으로 나눠 비균등한 크기의 두 리스트로 분할한다. 분할된 부분 리스트를 정렬한 다음 전체를 합쳐 정렬된 리스트를 얻는 방법이다.
(여기에서는 pivot을 가운데 지점으로 잡았지만 어느 위치든 가능하다.)
시간복잡도는 O(nlog₂n)이다.

5. 합병 정렬

func mergeSort(_ numbers: [Int]) -> [Int] {
    if numbers.count <= 1 {
        return numbers
    }
    
    let left = Array(numbers[0..<numbers.count / 2])
    let right = Array(numbers[(numbers.count / 2)..<numbers.count])
    
    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())
            }
        }
        
        if !left.isEmpty {
            result.append(contentsOf: left)
        }
        
        if !right.isEmpty {
            result.append(contentsOf: right)
        }
        return result
    }
    return merge(mergeSort(left), mergeSort(right))
}

하나의 리스트를 균등한 크기의 두 리스트로 분할하고 분할된 리스트를 정렬한 다음 정렬된 리스트를 합하여 전체가 정렬된 리스트가 되도록 만드는 방법이다.
합병 정렬은 분할 정복을 통해 이루어진다.
시간복잡도는 O(nlog₂n)이다.

6. 힙 정렬

func heapSort(_ numbers: [Int]) -> [Int] {
    var numbers = numbers
    
    func isLeaf(_ index: Int, _ maxIdx: Int) -> Bool {
        return maxIdx < 2 * index + 1
    }
    
    func makeSubHeap(_ root: Int, _ maxIdx: Int, _ numbers: inout [Int]) {

        var children = [numbers[2 * root + 1]]
        if maxIdx > 2 * root + 1 {
            children.append(numbers[2 * root + 2])
        }
        
        var bigIdx = 2 * root + 1
        
        if children.first! < children.last! {
            bigIdx += 1
        }
        
        if numbers[root] < numbers[bigIdx] {
            numbers.swapAt(root, bigIdx)
        }
    }
    
    func makeHeap(_ maxIdx: Int) {
        for i in stride(from: maxIdx, through: 0, by: -1) {
            if isLeaf(i, maxIdx) {
                continue
            }
            makeSubHeap(i, maxIdx, &numbers)
        }
    }
    makeHeap(numbers.count - 1)
    
    for i in stride(from: numbers.count - 1, to: 0, by: -1) {
        numbers.swapAt(0, i)
        makeHeap(i-1)
    }
    
    return numbers
}

최대 힙(내림차순)/최소 힙(오름차순) 트리를 구성해 정렬한다.
먼저 리스트를 완전 이진 트리 형태로 구성한다. 그 후 root에 있는 요소를 꺼내서 리스트의 맨 뒤로 이동시키고, 나머지로 다시 트리를 구성하여 마지막 요소가 남을 때까지 반복한다.
시간복잡도는 O(nlog₂n)이다.