sort() 함수
과거 알고리즘을 공부할 때 quick sort가 일반적으로 가장 좋은 퍼포먼스를 보인다고 배웠다..
기억대로 'swift 내장 sort? 그거 quick sort알고리즘 아닌감?...'
라고 생각했지만,, 이번 기회에 sort 알고리즘에 대해 찾아 보니 Tim sort라는 알고리즘을 사용한다고 한다..
tim sort란?
TimSort 는 insertion sort와 merge sort를 기반으로 하는 정렬 알고리즘,,
먼저 insertion sort를 사용하여 작은 조각을 정렬한 다음 merge sort를 사용하여 조각을 병합한다.
func timSort() {
print("Unsorted : \(arr)")
for i in stride(from: 0, to: arr.count, by: run) {
print("i : \(min((i + run),(arr.count)))")
arr.replaceSubrange(i..<min((i + run),(arr.count)), with: insertionSort(Array(arr[i..<min((i + run),(arr.count))])))
}
print("after insertion sort \(arr)")
var runCount = run
while runCount < arr.count{
for x in stride(from: 0, to: arr.count, by: 2 * runCount) {
print("x : \(x) runcount \(runCount) calc : \(x + 2 * runCount)")
arr.replaceSubrange(x..<min(x + 2 * runCount, arr.count), with: merge(leftPile: Array(arr[x..<min(x + runCount, arr.count)]), rightPile: Array(arr[min(x + runCount, arr.count)..<min(x + 2 * runCount, arr.count)])))
}
runCount = runCount * 2
}
print("Sorted : \(arr)")
}+) sort 기본 알고리즘은
introsort -> timsort -> modified timsort
로 바뀌었다고 한다
iOS