오늘은 빠른정렬에 대해 기록해 보려고 해요.
빠른정렬의 시간복잡도는 평균 O(nlog n)으로 O(n²)인 선택정렬보다
시간면에서 훨씬 유리해 많이 사용되는 방식입니다.
하지만 빠른정렬의 O(nlog n)은 '평균'이지 최악의 경우엔 O(n²)의 속도를 낼 수도 있습니다.
때에 따라서 적절하게 Merge Sort를 사용할 줄도 알아야 합니다.
코드 보면서 설명해 볼게요.
// 예를 들어 범위는 0~10까지 있다 가정
// 아래 뒤죽박죽의 배열을 0부터 10까지 순서대로 정렬
let arr = [8, 0, 2, 7, 10, 4, 6, 5, 3, 1, 9]
// 빠른정렬 함수 하나 만들고
func quickSort(_ arr: [Int]) -> [Int] {
if arr.count < 2 {
return arr // 배열의 개수가 2개보다 작다면? 이미 정렬된 상태라 봐도 됩니다.
} else {
// 기준이 될 값 하나 정합니다
let pivot = arr[0] // == arr.randomElement()
// 기준보다 작은 값
let less = arr.filter { $0 < pivot }
// 기준보다 큰 값
let larger = arr.filter { $0 > pivot }
return quickSort(less) + [pivot] + quickSort(larger)
}
}빠른정렬은 재귀함수에 대한 이해가 필요해요.
구글링 해보시고 브레이크 포인트 걸면서 디버깅 하면 이해가 되실 거에요.
이렇게 하고 프린트 찍어보시면
이렇게 정렬된 결과가 나옵니다.
머지소트는 좀 더 공부하고 게시해보도록 하겠습니다.
