위키피디아에 있는 정렬알고리즘을 비교한 표에서 일부를 확인해 보겠다.
위의 자료에서 여러 정렬 알고리즘의 시간복잡도를 확인할 수 있다.
마치 큰 수의 법칙처럼 정렬하고자 하는 배열의 크기가 충분히 크면 시간복잡도의 비교로
실제 정렬 시간을 비교할 수 있겠다.
하지만 주사위를 6번 던졌을 때 각 숫자가 한 번씩 나오지 않을 경우가 있는 것처럼
표본의 크기가 작을때는 얘기가 다를 수 있다.
예를 들어 Insertion sort를 보자. 해당 알고리즘의 평균 시간 복잡도는 (O=n^2)로
평균 시간 복잡도가 (O=n*logn)인 Quick sort보다 크다.
하지만 시간 복잡도가 (n^2)라는 것은 실제 값은 (C_i*n^2+R_i)이며,
(n*logn)라는 것은 (C_q*n*logn+R_q)이다.
즉, n이 작을때 (C_i,R_i,C_q,R_q) 값에 따라서 실제 수행시간은 역전이 될 수도 있다는 것이다.
위 자료는 보면 배열의 사이즈가 100이하일때는 Insertion sort가 실제 수행시간이 더 빠른 것을
확인할 수 있다.
그렇다면 (C_i,C_q)를 결정하는 요인은 무엇이 있을까?
큰 영향을 미치는 것중 하나는 참조 지역성[Locality of reference]이다.
참조 지역성이란 메모리 계층에 관련된 이야기이다.
연산을 처리하기 위해 최종적으로 CPU Register에 도달해야 한다.
레지스터에서는 캐시 메모리에 있는 데이터를 활용한다.
만약 CPU에서 다음에 처리하려고 하는 데이터가 캐시에 있지 않다면
메인메모리에서 캐시로 캐싱을 한 후에 사용해야 한다.
이때 중요한 점이 메인메모리에서 캐시로 캐싱하는 속도와
캐시에서 레지스터로 캐싱하는 속도의 차이가 크다는 점이다.
이 점을 유의하면서 참조 지역성으로 돌아가보자.
메인메모리에서 특정 주소를 사용한다면 근처 주소를 사용할 확률이 높기 때문에
함께 캐시로 캐싱하게 된다.
이후 실제로 근처 주소의 데이터를 참조하게 되면 메모리에서 캐시 하는 것보다는
성능을 크게 향상시킬 수 있다.
다음으로 정렬 알고리즘에서 참조 지역성을 이야기하는 이유는 뭘까?
Insertion sort의 경우 특정 주소의 데이터를 참조한 이후로 계속해서 그 근처의
값을 참조하게 된다. 즉, 미리 캐싱되어 있는 주소를 사용할 수 있고 메인 메모리와 IO 하는
수가 줄게 된다는 뜻이다.
Heap sort의 경우 특정 주소 참조 이후에 필요로 하는 주소와 이전 참조 주소와의 거리가 클 가능성이 크다.
즉, 메인 메모리와 IO 할 경우가 Insertion sort에 비해서 크다는 것이다.
이런 배경으로 위의 Quick sort와 Insertion sort의 수행속도 그래프의 결과를 만들게 된다.
Tim sort는 배열을 적당한 크기로 나누어 참조 지역성이 좋은 Insertion sort를 통해 정렬하고
이후 조각들을 Merge sort를 통해서 병합하는 정렬이다.
아래는 이전 글을 배경으로 작성한 Tim sort이다.
class TimSort<T: Comparable<T>>(
private val _insert: Insert<T>,
): SortingAlgorithm<T> {
companion object { const val minRun = 32 }
override val displayInfo: String = TIM_SORT_DISPLAY_INFO
override suspend fun sort(arr: MutableList<T>, low: Int, high: Int) {
for(i in low..high step(minRun)) {
timInsertionSort(arr, i, min(i + minRun - 1, high))
}
var size = minRun
while(size <= high) {
var tempLow = 0
while(tempLow <= high) {
val median = tempLow + size - 1
val tempHigh = min(tempLow + 2 * size - 1, high)
if(median < tempHigh) {
timMerge(arr, tempLow, median, tempHigh)
}
tempLow += 2 * size
}
size *= 2
}
}
private suspend fun timInsertionSort(arr: MutableList<T>, low: Int, high: Int) {
for(i in low+1.. high) {
val key = arr[i]
var j = i - 1
while(j >= low && arr[j] > key) {
_insert.insert(arr, j+1, arr[j])
j--
}
_insert.insert(arr, j+1, key)
}
}
private suspend fun timMerge(arr: MutableList<T>, low: Int, median: Int, high: Int) {
val leftLength = median - low + 1
val rightLength = high - median
val left = mutableListOf<T>()
val right = mutableListOf<T>()
for(i in low..high) {
if(i <= median) left.add(arr[i])
else right.add(arr[i])
}
var i = 0
var j = 0
var k = low
while(i < leftLength && j < rightLength) {
if(left[i] <= right[j]) {
_insert.insert(arr, k, left[i])
i++
}else {
_insert.insert(arr, k, right[j])
j++
}
k++
}
while(i < leftLength) {
_insert.insert(arr, k, left[i])
i++
k++
}
while(j < rightLength) {
_insert.insert(arr, k, right[j])
j++
k++
}
}
}
적당한 크기별로 나누어 Insertion sort를 하고 merge 해주는 것을 확인할 수 있다.
적당한 크기는 이 코드에서는 32로 설정해 줬다.
잘 구동되는 것도 확인했다.