-
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.퀵 정렬(quick sort)
가장 많이 사용되는 알고리즘
데이터의 특성을 파악하기 어렵다면 퀵 정렬이 유리
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식
피벗
사용 : 교환하기 위한 기준평균 시간 복잡도 $O(NlogN)$
그러나 최악의 경우 (데이터가 이미 정렬이 되어 있을 경우) O(N^2)이다
일반적 퀵 정렬 코드
var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] func quick_sort(array: inout [Int], start: Int, end: Int) { guard start < end else { return } let pivot = start var left = start + 1 var right = end while left <= right { while left <= end && array[left] <= array[pivot] { left += 1 } while right > start && array[right] >= array[pivot] { right -= 1 } if left > right { array.swapAt(right, pivot) } else { array.swapAt(left, right) } } quick_sort(array: &array, start: start, end: right - 1) quick_sort(array: &array, start: right + 1, end: end) } quick_sort(array: &array, start: 0, end: array.count - 1) print(array)
고차함수 사용 간결한 코드 (시간은 더 많이듦)
func quickSort(array: inout [Int]) -> [Int] { guard array.count > 1 else { return array } let pivot = array[0] let tail = array[1..<array.count] var leftSide = tail.filter { $0 <= pivot } var rightSide = tail.filter { $0 > pivot } return quickSort(array: &leftSide) + [pivot] + quickSort(array: &rightSide) }
시간 측정
0.00001406 → 일반적 퀵 정렬
0.0008339 → 고차함수 사용했을 때계수 정렬(count sort)
특정 조건이 부합될 때만 사용 가능
그러나 아주 빠르다 데이터 개수 N, 최댓값 K일 때 시간복잡도 $O(N+K)$
데이터의 크기 범위가 제한 되어 정수 형태로 표현 가능 할 때만 사용 가능
가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000을 넘지 않을 때 사용
→ 모든 범위의 수를 담을 수 있는 배열을 선언하기 때문
데이터가 0과 999,999와 같이 2개가 있을 때는 매우 비효율적
계수 정렬의 공간 복잡도는 O(N+K)
let array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] var count = Array(repeating: 0, count: array.max()! + 1) for i in 0..<array.count { count[array[i]] += 1 } for i in 0..<count.count { for _ in 0..<count[i] { print(i, terminator: " ") } } print()
swift 정렬 라이브러리
sort()나 sorted()를 사용할 수 있으며
sort는 기존 배열을 재정렬하며, sorted는 새로운 배열의 반환값이 있다.
둘 다 시간복잡도는 O(NlogN)을 보장
내부 구현은 Timsort로 구현되어 있다.
Timsort란 hybrid stable sorting algorithm으로
merge sort와 insert sort가 섞여있다.참고
https://velog.io/@hansangjin96/Swift-sort
https://book.naver.com/bookdb/book_detail.nhn?bid=16439154'알고리즘 > 이론' 카테고리의 다른 글
유클리드 알고리즘, 확장 유클리드 알고리즘 (0) 2021.04.20 최단 경로 (다익스트라, 플로이드 워셜 알고리즘) (0) 2021.03.14 부품 탐색 문제를 여러 알고리즘으로 풀어보기 with 시간 복잡도 (0) 2021.03.06 이진 탐색 (0) 2021.02.24