Timsort는 병합 정렬과 삽입 정렬의 개념을 사용하는 안정적인 정렬 알고리즘입니다. 삽입 정렬과 병합 정렬의 하이브리드 알고리즘이라고도 할 수 있습니다. Java, Python, C 및 C++ 내장 정렬 알고리즘에서 널리 사용됩니다. 이 알고리즘의 배경은 삽입 정렬을 사용하여 작은 청크를 정렬한 다음 병합 정렬 알고리즘의 병합 기능을 사용하여 모든 큰 청크를 병합하는 것입니다.
작업
이 알고리즘에서 배열은 작은 청크로 나뉩니다. 청크는 RUN으로 알려져 있습니다. 각 RUN은 삽입 정렬 기술을 사용하여 수행되고 정렬됩니다. 모든 RUN이 정렬된 후 병합 기능을 사용하여 병합됩니다.
어레이의 크기가 RUN보다 작을 수 있는 경우가 있을 수 있습니다. 이러한 경우 배열은 삽입 정렬 기술로 정렬됩니다. 일반적으로 RUN 청크는 어레이의 크기에 따라 32에서 64까지 다양합니다. 병합 기능은 하위 배열 청크의 크기가 2의 거듭제곱인 경우에만 병합됩니다.
삽입 정렬을 사용하는 이점은 작은 크기의 배열에 대해 삽입 정렬이 잘 작동하기 때문입니다.
시간 복잡도 -
-
베스트 케이스 - Omega(n)
-
평균 케이스 - O(nlogn)
-
최악의 경우 - O(nlogn)
Tim Sort 알고리즘
-
32 크기로 RUN을 초기화합니다.
-
RUN 크기 청크에 대한 삽입 정렬을 구현합니다.
-
merge(int arr[], int l, int m, int r) 함수는 배열, 왼쪽 요소, 배열의 중간 및 배열의 오른쪽 요소를 입력으로 사용합니다. 이 함수는 크기가 32인 병합된 정렬 청크를 반환합니다.
-
왼쪽 요소가 모두 포함된 배열의 길이와 오른쪽 요소가 모두 포함된 배열의 길이를 초기화합니다.
-
왼쪽 배열과 오른쪽 배열을 채운 후 왼쪽 배열과 오른쪽 배열을 반복합니다.
-
왼쪽 배열의 요소가 오른쪽 배열의 요소보다 작으면 요소를 더 큰 배열로 푸시합니다.
-
그렇지 않으면 그에 따라 요소를 더 작은 배열로 푸시합니다.
-
왼쪽 배열과 오른쪽 배열의 나머지 요소를 더 큰 배열로 복사합니다.
-
timSortAlgo(int arr[], int n) 함수는 배열과 그 크기를 입력으로 받습니다. 처음에 삽입 정렬을 호출하고 배열 요소를 병합합니다.
-
팀 정렬을 사용하여 출력을 배열의 마지막 요소로 반환합니다.
예시(C++)
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // Initialising the RUN to get chunks
void insertionSort(int arr[], int left, int right) // Implementing insertion
sort for RUN size chunks{
for (int i = left + 1; i <= right; i++){
int t = arr[i];
int j = i - 1;
while (j >= left && t < arr[j]){
arr[j+1] = arr[j--];
}
arr[j+1] = t;
}
}
void merge(int arr[], int l, int m, int r) // using the merge function the
sorted chunks of size 32 are merged into one{
int len1 = m - l + 1, len2 = r - m;
int left[len1], right[len2];
for (int i = 0; i < len1; i++)
left[i] = arr[l + i]; // Filling left array
for (int i = 0; i < len2; i++)
right[i] = arr[m + 1 + i]; // Filling right array
int i = 0;
int j = 0;
int k = l;
while (i < len1 && j < len2) // Iterate into both arrays left and right{
if (left[i] <= right[j]) // IF element in left is less then increment i by pushing into larger array{
arr[k] = left[i];
i++;
} else {
arr[k] = right[j]; // Element in right array is greater
increment j
j++;
}
k++;
}
while (i < len1) // This loop copies remaining element in left array{
arr[k] = left[i];
k++;
i++;
}
while (j < len2) // This loop copies remaining element in right array{
arr[k] = right[j];
k++;
j++;
}
}
void timSortAlgo(int arr[], int n){
for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //Call insertionSort()
for (int s = RUN; s < n; s = 2*s) // Start merging from size RUN (or 32). It will continue upto 2*RUN{
// pick starting point of left sub array. We are going to merge
arr[left..left+size-1]
// and arr[left+size, left+2*size-1]
// After every merge, we
// increase left by 2*size
for (int left = 0; left < n;left += 2*s){
int mid = left + s - 1; // find ending point of left sub
array mid+1 is starting point of right sub array
int right = min((left + 2*s - 1), (n-1));
merge(arr, left, mid, right); // merge sub array
arr[left.....mid] & arr[mid+1....right]
}
}
}
void printArray(int arr[], int n){
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Main function to implement timsort algorithm
int main(){
int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The Original array- ";
printArray(arr, n);
// calling the timsortAlgo function to sort array
timSortAlgo(arr, n);
cout<<"After Sorting Array Using TimSort Algorithm- ";
printArray(arr, n); // Calling print function
return 0;
}