[Algorithm] 퀵 정렬, 병합 정렬 알고리즘(Swift 구현)

[Algorithm] 퀵 정렬, 병합 정렬 알고리즘(Swift 구현)

 

퀵 정렬(Quick Sort)은 많이 사용되는 알고리즘이다. 더불어 병합 정렬(Merge Sort)도 많이 쓰인다. 두 정렬 알고리즘은 삽입, 선택 정렬보다 훨씬 빠른 속도로 정렬되기 때문에 대부분의 프로그래밍 언어에서 정렬 라이브러리에서 활용되기도 한다.

 

현재 정렬 알고리즘의 근간이 되는 두 정렬을 이번 포스팅에서는 알아볼 것이다.

 

 

1. 퀵 정렬(Quick Sort)

 

1) 정의

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 방법

 

2) 설명

 

(1) 과정 설명

 

정의만으로는 이해하기가 어렵다. 상세히 설명을 해보겠다.

퀵 정렬은 '분할 정복' 방법으로 리스트를 정렬하는 것이다.

 

(오름차순 기준)

(1) 리스트에서 첫 번째 데이터를 피벗(기준)으로 정한다.

(2) 리스트 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 그 두 데이터의 위치를 서로 교환해 준다. 계속 반복하다가, 왼쪽에서부터 찾은 데이터와 오른쪽에서부터 찾은 데이터의 위치가 서로 엇갈릴 수 있다.

ex. 
5 4 2 0 3 1 6 9 7 8
5가 피벗인데, 왼쪽에서부터 찾은 큰 데이터가 6일 것이고, 오른쪽에서부터 찾은 데이터가 1이다. 이것이 데이터의 위치가 엇갈리는 상황이다.

엇갈리게 되었을 때, 작은 데이터의 위치(예시에서 1)와 피벗(5)의 위치를 바꿔준다. 그렇게 되면 예시로 든 리스트는 다음과 같이 분할된다.

1 4 2 0 3 5 6 9 7 8

피벗인 5를 기준으로 좌측은 5보다 작은 수, 우측은 5보다 큰 수로 배열이 된 것을 알 수 있다. 이것을 '분할'이라고 한다.

(4) 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 좌측 리스트와 우측 리스트로 나누어 재귀적으로 과정을 반복하는 것이다.

[1 4 2 0 3] [6 9 7 8] 두 개의 리스트로 나뉘어 분할을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

분할과 재귀를 활용한 방법으로 정렬이 이루어지는 것을 알 수 있다. 피벗은 가장 왼쪽의 것을 피벗으로 삼기도 하고, 임의로 선정하기도 한다.

 

 

(2) 시간 복잡도, 공간 복잡도

 

시간복잡도의 경우, 평균적으로 O(NlogN)이다. 피벗값의 위치가 변경되어 분할이 일어날 때마다 왼쪽과 오른쪽 리스트를 '절반'씩 나눈다고 생각해보면 이해를 할 수 있다. 8개의 데이터가 있을 때, 데이터는 4, 4개로 나누어질 것이고, 그다음은 2 2 2 2개, 그다음은 1 * 8 개로 나누어질 것이다. 분할이 이루어지는 횟수가 기하급수적으로 감소하게 됨을 알 수 있다. 

 

최악의 경우에는 O(N2) 시간이 걸린다. 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작할 수 밖에 없다. 데이터가 무작위로 입력되는 경우, 퀵 정렬은 빠르게 동작할 확률이 '높다'.

 

그래서 C++은 최악의 경우에도 시간복잡도가 O(NlogN)이 될 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해주기도 한다.

 

공간복잡도의 경우, 주어진 배열 안에서 Swap을 통해 정렬이 수행되기에 O(N)이다.

 

 

4) Swift 코드

 

(1) 반복문을 사용한 코드

func quickSort(_ list: inout [Int], _ lo: Int, _ hi: Int) {
    if lo < hi {
        let pivot = partition(&list, lo: lo, hi: hi)
        
        quickSort(&list, lo, pivot)
        quickSort(&list, pivot + 1, hi)
    }
}

func partition(_ list: inout [Int], lo: Int, hi: Int) -> Int {
    let pivot = list[lo]
    var i = lo - 1
    var j = hi + 1
    
    while true {
        i = i + 1
        while list[i] < pivot { i = i + 1 }
        j = j - 1
        while list[j] > pivot { j = j - 1 }
        if i >= j {
            return j
        }
        list.swapAt(i, j)
    }
}

 

 

2) filter()를 사용한 코드

func quickSort(_ array: [Int]) -> [Int] {
    guard let first = array.first, array.count > 1 else { return array }
 
    let pivot = first
    let left = array.filter({ $0 < pivot })
    let right = array.filter({ $0 > pivot })
    
    return quickSort(left) + [pivot] + quickSort(right)
}

 

filter를 사용하면 O(2N) 시간이 걸린다는 차이가 있다.

 

 

2. 병합 정렬(Merge Sort)

1) 정의

분할 정복 방법을 통해 구현하는 것으로 리스트를 쪼갤 수 있을 만큼 쪼개고 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 

피벗을 통해 정렬을 하여 분할한 후 재귀적으로 그 시퀀스를 반복하는 퀵 정렬과 순서에 있어서 차이가 있는 정렬이라고 할 수 있다.

 

큰 문제를 작은 문제로 나눈 뒤 작은 문제를 해결하여 최종적으로 큰 문제를 해결하는 다이나믹 프로그래밍 방식과 같다고 할 수 있다.

 

2) 설명

 

(1) 과정 설명

(오름차순 기준)

(1) 위의 예시를 보면 1 ~ 8까지의 원소들이 랜덤으로 배치되어 있다. 원소는 8개이기 때문에, 길이가 1인 리스트로 쪼개려면 총 3번의 Divide가 있으면 된다.

(2) 3번의 Divide를 하면 6 5 3 1 8 7 2 4로 나누어지는데, 이것들을 차례로 병합하면서 정렬을 이루어 나가는 것이다.

(3) 첫 번째 병합은 다음과 같이 이루어진다.
6과 5를 비교 / 3과 1을 비교 / 8과 7을 비교 / 2와 4를 비교한다. 
그러면 5, 6 / 1, 3 / 7, 8 / 2, 4 로 1차 정렬이 완료된다.

(4) 두 번째 병합은 5, 6 - 1, 3 / 7, 8 - 2, 4를 정렬한다.
먼저 5와 1을 비교한다. 1이 먼저 위치해야 하니 1을 둔다. 그다음에는 5와 3을 비교한다. 3이 먼저 와야 하니 3이 1 뒤에 위치한다. 그다음은 5, 6은 이미 정렬되어 있으니 순서대로 위치한다. 그러면 5, 6, 1, 3은 [1, 3, 5, 6]으로 정렬이 된다.

마찬가지로 우변도 정렬 과정을 거치면 [2, 4, 7, 8]이 된다.

두 번째 병합을 거친 결과, [1, 3, 5, 6, 2, 4, 7, 8]이 된다.

(5) 세 번째 병합은 1, 3, 5, 6 / 2, 4, 7, 8로 나누어서 병합을 시행한다.

먼저 1, 2를 비교한다. 1이 작기 때문에 먼저 위치한다.
그 다음은 3과 2를 비교한다. 2가 작기 때문에 2가 위치한다.
그다음은 3과 4를 비교한다. 3이 작기 때문에 3이 위치한다.
4와 5를 비교한다. 
.....
마지막으로 우변에만 7, 8이 남게 된다. 정렬된 리스트에 그 두 개의 원소를 붙이면
[1, 2, 3, 4, 5, 6, 7, 8]로 정렬이 되게 된다.

 

Divide와 Conquer를 하고, Combine의 과정을 거쳐서 정렬이 되는 것을 알 수 있다.

합병 정렬은 추가적인 리스트가 필요하다. 복사의 과정을 거치기 때문에, 이전의 Swap 방식을 활용하는 정렬보다는 메모리가 더 필요하다.

 

분할 과정은 실제로 한 개의 리스트로 만들어서 무엇을 할 필요가 없을 것이다. index를 활용하면 되기 때문이다.

 

 

(2) 시간 복잡도, 공간 복잡도

 

병합 정렬은 최선, 평균, 최악의 시간복잡도가 모두 O(NlogN)이다.

분할 단계에서는 비교, 이동 연산이 수행되지 않는다. 

 

길이가 8인 배열은 3번의 과정을 거쳐 분할되었는데, 병합의 과정도 3번의 과정을 거쳐야 함을 알 수 있다.

그러면 '단계의 높이'가 logN이라고 할 수 있다. (위의 예시에서는  밑이 2인 로그 8 이므로, 3)

 

그러면 각 단계에서 필요한 정렬의 횟수는 몇 번일까?

위에서 설명한 예시를 살펴보자.

(3) 첫 번째 병합은 다음과 같이 이루어진다.
6과 5를 비교 / 3과 1을 비교 / 8과 7을 비교 / 2와 4를 비교한다. 
그러면 5, 6 / 1, 3 / 7, 8 / 2, 4로 1차 정렬이 완료된다.

5, 6, 1, 3을 정렬하려면? [5 - 1 / 5 - 3 / 3 - 5 / 5 - 6] 이렇게 비교를 하여야 한다.

최대 N번의 확인을 거친 후 정렬이 되는 것이다.

1, 3이 먼저 정렬된 후, 3과의 비교를 통해 좌변이 정렬되는 것을 보면, 우변도 동일하게 최대 4번 정도의 비교가 있어야 정렬이 된다는 것을 을 추측해 볼 수 있다.

 

그렇다면?

 

N * logN 이 시간복잡도가 되는 것이라고 결론을 내려볼 수 있는 것이다.

 

한편, 공간복잡도의 경우, 병합할 곳의 새로운 배열을 생성해주어야 한다. 정렬할 배열과 같은 크기(O(N))의 새로운 배열이 필요하다. 따라서 공간복잡도는 O(2N) = O(N)이라고 할 수 있다.

 

 

3) Swift 코드

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

 

 

3. 정리

 

내장 라이브러리에서 활용되는 퀵 정렬과 병합 정렬에 대해 알아보았다.

선택 정렬, 삽입 정렬보다 훨씬 빠르게 동작할 수 있는 이유에 대해 알 수 있었다. 어떤 기준을 가지고 정렬을 하거나 쪼개서 병합을 하는 방식에서 기하급수적으로 비교 횟수가 줄어드는 이유로 더 빠르게 동작한다고 할 수 있겠다.

 

4개의 정렬을 알아보았는데, 설명을 제대로 안한 것이 하나 있었다.

 

안정 정렬, 불안정 정렬 개념인데, 퀵 정렬은 불안정 정렬이고 병합 정렬은 안정 정렬이다.

이전에 궁금했던 정렬할 때 이전의 순서가 바뀌는지 바뀌지 않는지에 대해 궁금했던 부분이 바로 이 부분이다.

 

다음 편에는 안정, 불안정 정렬을 다루어보고, 힙 정렬, 기수 정렬, 계수 정렬, 팀 정렬을 차례로 다뤄볼 예정이다.

 

그럼!