What's the fundamental meaning of Tim Sort?
Tim Sort는 이름에 의미가 있는 것이 아닌 Tim 이란 분께서 만든 정렬 알고리즘입니다. 흔히 알고 있는 정렬 알고리즘 중 알아야 하는 것은 크게 Bubble Sort,Insertion Sort,Heap Sort,Merge Sort,Quick Sort가 있습니다. 이 중 Insertion Sort와 Merge Sort 이 두개의 정렬을 합쳐 만든 개념 입니다.
- Time Complexity inside of Tim Sort
- Insertion Sort : O(n^2), stable
- Merge Sort : O(nlogn), stable but it takes a bunch of memory → O(n)
해당 두 알고리즘은 느린 알고리즘과 상대적으로 빠른 알고리즘으로 알려져 있습니다. 시간 복잡도라는 것을 자세히 떠올려 보면 Merge Sort의 경우 실제 동작 시간은 C X nlogn + a라는 의미를 가지고 있습니다. log 앞에 붙어 있는 상수에 의해 동작 시간이 크게 변할 수 있음을 나타낸다. 이때, C 라는 값에 큰 영향을 끼치는 요소로 알고리즘이 참조지역성원리를 얼마나 잘 만족하는 지를 볼 수 있습니다.
💡 참조지역성원리란?
CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 즉, 이론적으로 도입이 되어 사용되는 알고리즘이 현실에서 얼마나 걸릴지 예측하기 위해서 사용이 되는 상수값이다.
참조지역성에 따르면 Tim Sort 이전에 완전히 만족하는 정렬이 없을 때 해당 알고리즘이 등장하게 됩니다. Tim Sort는 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)입니다. Insertion Sort, Merge Sort를 결합한 정렬 방식이기 때문에 훨씬 안정적이며 참조지역성을 만족하지만 메모리를 과도하게 사용하는 문제가 있던 Merge Sort의 문제를 어느 정도 개선한 알고리즘입니다.
Basics of Tim Sort
Insertion Sort는 인접한 메모리(변수의 값)과 비교를 하여 반복을 진행하기 때문에 참조지역성의 원리를 잘 만족하고 있는 것을 확인 할 수 있습니다.(참조지역성을 만족한다는 것은 Spatial locality, Temporal locality, Sequential locality를 잘 만족하는 정렬 알고리즘이라는 의미입니다.) Insertion Sort와 Quick Sort를 비교하여 봤을 때 대량의 데이터를 다루는데 있어 효율적인 것은 Quick Sort가 맞지만, 작은 레코드를 다루는데에는 Insertion Sort가 유리하기 때문에(C_i ✖️ n^2 < C_q ✖️ nlogn == true) 이러한 장점을 이용하여 작은 데이터 부터 큰 데이터를 전부 쉽게 정렬하기 위해서 만들어진 원리입니다. 이때 정렬함에 있어 원할하게 동작시키기 위해서 최적화를 진행합니다.
The method of Optimizing Tim Sort
Tim Sort는 Insertion Sort 와 Merge Sort의 결합이기 때문에 C_m ✖️ n(log(n - x) + a)가 됩니다. 이때, x를 최대한 크게 하고 a값을 최대한 줄이기 위해서 주어진 배열을 2^x 개씩 잘라서 Insertion Sort로 정렬하되 이후는 정렬하기 않고 자른 덩어리를 최대한 크게 만들어 병합 횟수를 줄이는 방법을 채택했습니다.
Interim summary
주어진 배열을 잘라 Insertion Sort를 하기 위해서 minrun을 정해야 합니다. 보통의 경우 배열의 중간 값을 이용해서 자르게 됩니다. minrun을 통해서 잘려진 덩어리를 run이라고 부르됩니다.
Tim Sort 에서 전체 원소의 개수를 N이라 할때, minrun의 크기를 min(N, 2^5 ~ 2^6)로 정의합니다. 고정된 수로 정의하지 않는 이유는 경우에 따라 성능이 저하가 되는 일이 생기기도 하기 때문입니다. 외부적으로 minrun의 값은 공개가 되지 않고 API 등을 참고하여 확인해야 합니다. 이러한 원리를 이용하여 작은 배열에서는 원소의 개수를 따라 값을 고정하고 그 이상이 되는 경우에는 2^6이 되거나 그대로 유지 되거나 하는 방식입니다.
Binary Insertion Sort
Tim Sort에서 사용하는 Insertion Sort는 Binary Insertion Sort 입니다. 삽입해야 할 위치를 찾을 때까지 원소를 비교하는 대신, 앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색을 진행하여 위치를 찾습니다. 이분탐색 자체는 참조지역성이 떨어지지만, 전체적인 연산의 속도를 두고 봤을 때는 훨씬 효율적이게 됩니다.
- Insertion Sort
void insertionSort(int[] a, int size) {
for(int i = 1; i < size; i++) {
// 타겟 넘버
int target = a[i];
int j = i - 1;
// 타겟이 이전 원소보다 크기 전 까지 반복
while(j >= 0 && target < a[j]) {
a[j + 1] = a[j]; // 이전 원소를 한 칸씩 뒤로 미룬다.
j--;
}
a[j + 1] = target;
}
}- Binary Insertion Sort
void insertionSort(int[] a, int size) {
for(int i = 1; i < size; i++) {
// 타겟 넘버
int target = a[i];
// 0 ~ i 사이 이분탐색을 통해 target이 배치 될 위치를 반환
int location = binarySearch(a, 0, i, target);
int j = i - 1;
while(j >= location) {
a[j + 1] = a[j]; // 이전 원소를 한 칸씩 뒤로 미룬다.
j--;
}
a[location] = target;
}
}- Binary Search
- Coding with for loops
public static boolean BSearch(int[] arr, int n) {
int left = 0;
int right = arr.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] < n) left = mid + 1;
else if (arr[mid] > n) right = mid - 1;
else return true;
}
return false;
}- Coding with Recursion
public static boolean BSearchRecursive(int[] arr, int n, int left, int right) {
if(left > right) return false;
int mid = (left + right) / 2;
if (arr[mid] < n)
return BSearchRecursive(arr, n, mid +1, right);
else if (arr[mid] > n)
return BSearchRecursive(arr, n, left, mid - 1);
else
return true;
}Merge Sort의 과정
배열이 주어짐에 따라 Tim Sort는 먼저 Min Sort 값을 결정합니다.(이를 정하는 기준은 배열의 크기에 따라 min(N, 2^5 ~ 2^6)으로 결정됩니다.) 이렇게 결정된 minrun으로 배열을 잘라서 작은 Run으로 나누게 됩니다.(Run은 덩어리를 말합니다.)
나눠진 두개의 배열을 Insertion Sort를 통해서 정렬을 하고 나눠진 두개의 Run을 합치게 됩니다. 그렇게 최종 합병이 되어 정렬이된 배열이 출력되게 됩니다.
References
1. Tim sort_1
2. Tim sort_2
3. Binary Search
4. Binary Search_2
