Timsort là một thuật toán sắp xếp ổn định sử dụng ý tưởng sắp xếp hợp nhất và sắp xếp chèn. Nó cũng có thể được gọi là một thuật toán kết hợp giữa sắp xếp chèn và hợp nhất. Nó được sử dụng rộng rãi trong các thuật toán sắp xếp sẵn có của Java, Python, C và C ++. Ý tưởng đằng sau thuật toán này là sắp xếp các phần nhỏ bằng cách sử dụng sắp xếp chèn và sau đó hợp nhất tất cả các phần lớn bằng cách sử dụng chức năng hợp nhất của thuật toán sắp xếp hợp nhất.
Đang làm việc
Trong thuật toán này, mảng được chia thành các phần nhỏ. Các khối được gọi là RUN. Mỗi RUN được lấy và sắp xếp bằng cách sử dụng kỹ thuật sắp xếp chèn. Sau khi tất cả các RUN được sắp xếp, chúng được hợp nhất bằng cách sử dụng chức năng hợp nhất.
Có thể có trường hợp kích thước của mảng có thể nhỏ hơn RUN. Trong trường hợp này, mảng được sắp xếp theo kỹ thuật sắp xếp chèn. Thông thường, đoạn RUN thay đổi từ 32 đến 64 tùy thuộc vào kích thước của mảng. Hàm hợp nhất sẽ chỉ hợp nhất nếu đoạn mảng con có kích thước quyền hạn là 2.
Ưu điểm của việc sử dụng sắp xếp chèn là vì sắp xếp chèn hoạt động tốt cho mảng có kích thước nhỏ.
Độ phức tạp về thời gian -
-
Trường hợp tốt nhất - Omega (n)
-
Trường hợp trung bình - O (nlogn)
-
Trường hợp tệ nhất - O (nlogn)
Các thuật toán của Tim Sort
-
Khởi tạo RUN với kích thước là 32.
-
Triển khai sắp xếp Chèn cho các khối kích thước RUN.
-
Hợp nhất một hàm (int arr [], int l, int m, int r) lấy một mảng, các phần tử bên trái, giữa mảng và các phần tử bên phải của mảng làm đầu vào. Hàm trả về các khối được sắp xếp đã hợp nhất có kích thước 32.
-
Khởi tạo độ dài của mảng có tất cả các phần tử bên trái và độ dài của mảng có tất cả các phần tử bên phải.
-
Sau khi điền vào mảng bên trái và mảng bên phải, hãy lặp lại trên mảng bên trái cũng như mảng bên phải.
-
Nếu phần tử trong mảng bên trái nhỏ hơn phần tử trong mảng bên phải, hãy đẩy phần tử vào một mảng lớn hơn.
-
Nếu không, hãy đẩy phần tử vào một mảng nhỏ hơn cho phù hợp.
-
Sao chép phần tử còn lại trong mảng bên trái và mảng bên phải vào một mảng lớn hơn.
-
Một hàm timSortAlgo (int arr [], int n) nhận một mảng và kích thước của nó làm đầu vào. Lệnh này gọi chèn Sắp xếp ban đầu và hợp nhất các phần tử mảng.
-
Trả về đầu ra dưới dạng các phần tử cuối cùng của mảng bằng cách sử dụng Tim Sort.
Ví dụ (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;
}