신속 정렬
퀵 정렬도 합병 정렬처럼 분할 정복에 근거하여 만들어진 정렬 방식입니다. 따라서, 정렬 대상을 반씩 줄여나가는 과정을 포함하고 있습니다. 퀵 정렬은 임의의 기준수 pivot을 선택하여 pivot보다 작은 그룹과 큰 그룹으로 분할합니다. 그리고, 그룹 안에서 기준수 pivot을 정하고 다시 작은 그룹과 큰 그룹으로 분할하는 과정을 반복합니다. 더이상 분할할 수 없는 상태가 되면 정렬이 완료됩니다.
원리
⓵ 가장 앞에 위치한 요소를 pivot으로 설정합니다.
⓶ pivot을 제외한 다른 값들을 큰 값, 작은 값으로 나누기 위해서 인덱스 변수를 둡니다.
⓷ low 인덱스는 맨 앞에서부터 시작하며 pivot보다 큰 값을 만나면 해당 인덱스에 멈춥니다.
⓸ high 인덱스는 맨 뒤에서부터 시작하며 pivot보다 작은 값을 만나면 해당 인덱스에 멈춥니다.
⓹ low, high 모두 더이상 움직이지 못하는 상태가 되면 두 값을 바꿉니다.
⓺ low > high 인 상태가 되면 하던 것을 멈추고 pivot과 high 자리에 있는 값을 바꿉니다.
⓻ pivot을 제외한 왼쪽, 오른쪽 리스트를 대상으로 위의 과정을 반복합니다.
*더이상 리스트를 분할할 수 없을 때까지 반복
매번 pivot보다 큰 값과 작은 값으로 리스트가 분할되기 때문에 high와 자리를 바꾼 pivot은 제 위치로 가게 됩니다. pivot은 항상 정렬되게 됩니다.
예시
신속 정렬을 그림으로 나타내봤습니다. 주어진 배열 [8, 25, 3, 12, 5, 19, 7]를 신속 정렬을 사용해서 정렬해봤습니다.
QuickSort.swift
퀵 정렬 코드를 이렇게 구현해봤습니다.
quickSort 함수는 더이상 분할이 안될 때까지 분할을 하는 역할을 합니다.
func quickSort(_ list: inout [Int], low: Int, high: Int) {
if low < high { // ⓵
let pivot = partition(&list, low: low, high: high) // ⓶
quickSort(&list, low: low, high: pivot - 1) // ⓷
quickSort(&list, low: pivot + 1, high: high) // ⓸
}
}
Swift
복사
⓵ low가 high보다 작아서 분할이 가능한 상태일 때, 하단의 코드를 실행합니다.
먼저, ⓶ partition함수를 사용해서 pivot의 위치를 가져옵니다. 그리고, 해당 위치를 기점으로 양 옆에 있는 요소들을 정렬하기 위해서 다시 quickSort 함수를 호출합니다. 이번에는 ⓷ 가져온 pivot 위치보다 앞에 있는 리스트와 ⓸ 가져온 pivot 위치보다 뒤에 있는 리스트를 차례대로 호출합니다.
리스트를 어떻게 분할하는지는 quickSort 함수를 통해서 봤으니깐, 어떻게 분할한 리스트를 정렬해나가는지 확인해봅시다. 해당 과정은 partition에 있습니다.
func partition(_ list: inout [Int], low: Int, high: Int) -> Int {
let pivot = list[low] // ⓵
var i = low - 1, j = high + 1 // ⓶
while true {
i += 1
while list[i] < pivot { i += 1 } // ⓷
j -= 1
while list[j] > pivot { j -= 1 } // ⓸
if i >= j { return j } // ⓹
list.swapAt(i, j) // ⓺
}
}
Swift
복사
먼저, ⓵ 리스트의 pivot을 맨 앞에 있는 값으로 설정합니다. 그리고, ⓶ low, high 값을 대신할 i, j를 만들어 줍니다. 각 변수는 현재 위치에서 앞, 뒤로 한 칸씩 옮겨줬습니다. while문이 시작하면 바로 원하는 인덱스부터 시작할 수 있게 말이죠.
while문으로 들어가면 먼저 low에 해당하는 i에 위치를 앞으로 한 칸 옮기고 ⓷ 해당 값이 pivot보다 클 때까지 while문을 돕니다. 해당 값을 찾으면 while문이 멈춥니다. 다음엔 high에 해당하는 j의 위치를 뒤로 한 칸 옮기고 ⓸ 해당 값이 pivot보다 작을 때까지 while문을 돕니다. 해당 값을 찾으면 while문이 멈춥니다.
만약, ⓹ i가 j보다 크거나 같아진다면 해당 j 값이 pivot의 위치이기 때문에 해당 값을 리턴해줍니다. 아니라면, 이전에 찾은 두 값을 swap 합니다. 그리고, i가 j보다 커질 때까지 위의 작업을 반복합니다.
간단한 QuickSort.swift
위의 방식보다 간단하게 퀵 정렬을 작성할 수도 있습니다.
func quicksort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else { return arr }
let pivot = arr[arr.count/2] // ⓵
let less = arr.filter { $0 < pivot } // ⓶
let equal = arr.filter { $0 == pivot } // ⓷
let greater = arr.filter { $0 > pivot } // ⓸
return quicksort(less) + equal + quicksort(greater) // ⓹
}
Swift
복사
먼저, ⓵ 기준값(pivot)을 배열의 중간에 있는 값으로 설정합니다. 그리고, 해당 기준값보다 ⓶ 작은 값을 필터링하여 less에 집어 넣습니다. 해당 기준값보다 ⓸ 큰 값은 필터링하여 greater에 집어 넣습니다. 기준값과 ⓷ 같은 값은 equal에 집어 넣습니다.
마지막으로 ⓹ 기준값보다 작은 그룹과 큰 그룹을 완전히 분할될때까지 분할하기 위해서 quicksort함수에 다시 한 번 집어 넣습니다. 그리고, 배열 가운데에는 기준값이 위치하도록 합니다.
위에서 작성한 코드를 간단하게 filter 메서드를 사용해서 구현할 수 있습니다.
시간 복잡도
퀵 정렬의 시간 복잡도는 최선과 최악의 상황에서 차이가 납니다.
parition 함수에 있는 비교 연산을 통해서 설명을 해보겠습니다.
func partition(_ list: inout [Int], low: Int, high: Int) -> Int {
let pivot = list[low]
var i = low - 1, j = high + 1
while true {
i += 1
while list[i] < pivot { i += 1 } // ⓵
j -= 1
while list[j] > pivot { j -= 1 } // ⓶
if i >= j { return j }
list.swapAt(i, j)
}
}
Swift
복사
partition에는 2개의 주요한 비교 연산이 존재합니다. ⓵ 해당 값이 pivot 보다 작은지, ⓶ 해당 값이 pivot 보다 큰 지를 확인하는 부분입니다. pivot이 자리를 찾기 위해서는 모든 값과의 비교를 진행해야 합니다.
즉, n개의 요소들이 배열에 들어있다면, 최대 n만큼의 비교 연산을 진행해야 합니다.
그럼, 몇 번의 비교 연산을 반복하는 걸까요?
분할될 때마다 분할된 서브리스트에서 비교 연산이 다시 진행됩니다.
위에서도 7개의 요소를 비교하기 위해서 3단계의 퀵 정렬이 발생했습니다.
[8, 25, 3, 12, 5, 19, 7]에서 [5, 7, 3] [8] [12, 19, 25]로 분할하고 [3] [5] [7] [8] [12] [19, 25]로 다시 분할하는 3단계를 거쳤습니다.
즉, 퀵 정렬도 합병 정렬과 동일하게 n개의 요소들이 배열에 있으면 만큼 비교 연산이 반복됩니다.
● 결론적으로, 이 걸리게 됩니다.
하지만, 최악의 상황에서는 의 시간 복잡도가 발생합니다.
바로, 완전히 정렬된 배열을 퀵 정렬에 넣는 상황에서 최악의 시간 복잡도가 나타날 수 있습니다.
퀵 정렬에서 맨 앞에 있는 값을 pivot으로 사용하게 됩니다. 그런데, 해당 값이 배열에서 가장 작은 값이었다면 나중에 큰 값, 작은 값으로 나누게 되었을 때 모든 값들이 큰 값으로 몰리게 됩니다.
즉, 작은 그룹은 텅 비고 큰 그룹에는 모든 요소들이 들어가게 됩니다. 비효율적으로 동작하게 되는겁니다.
그런 상황에서는 비교 연산에 드는 만큼에 서브 리스트를 만큼 반복해야 하기 때문에 의 시간 복잡도가 들게 됩니다.
이를 해결하기 위해서는 앞이나 뒤에 있는 요소를 pivot으로 잡지 말고, 중앙값을 피봇으로 설정해서 최악의 시간 복잡도를 피할 수 있도록 만들 수 있습니다.
10000개의 원소가 들어있는 배열을 정렬할 때에 어느정도의 시간복잡도가 드는지 확인해보겠습니다.
•
신속 정렬(정렬된 상태)
•
신속 정렬(거꾸로 정렬된 상태)
완벽하게 정렬되지 않은 배열이 정렬된 배열보다 빠르게 정렬되는걸 확인할 수 있습니다.
+⍺
퀵 정렬 관련 코드는 깃허브에 올려뒀습니다.