टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है जो मर्ज सॉर्ट और इंसर्शन सॉर्ट के विचार का उपयोग करता है। इसे इंसर्शन और मर्ज सॉर्ट का हाइब्रिड एल्गोरिदम भी कहा जा सकता है। यह जावा, पायथन, C, और C++ इनबिल्ट सॉर्ट एल्गोरिदम में व्यापक रूप से उपयोग किया जाता है। इस एल्गोरिदम के पीछे विचार इंसर्शन सॉर्ट का उपयोग करके छोटे चंक्स को सॉर्ट करना और फिर मर्ज सॉर्ट एल्गोरिदम के मर्ज फ़ंक्शन का उपयोग करके सभी बड़े चंक्स को मर्ज करना है।
कार्यप्रणाली
इस एल्गोरिदम में, एरे को छोटे चंक्स में विभाजित किया जाता है। चंक्स को RUN के रूप में जाना जाता है। प्रत्येक RUN को लिया जाता है और इंसर्शन सॉर्ट तकनीक का उपयोग करके सॉर्ट किया जाता है। सभी RUN सॉर्ट हो जाने के बाद, इन्हें मर्ज फ़ंक्शन का उपयोग करके मर्ज किया जाता है।
ऐसा मामला हो सकता है जहां एरे का आकार RUN से कम हो। ऐसे मामले में, एरे को इंसर्शन सॉर्ट तकनीक द्वारा सॉर्ट किया जाता है। आमतौर पर, RUN चंक एरे के आकार के आधार पर 32 से 64 तक भिन्न होता है। मर्ज फ़ंक्शन केवल तभी मर्ज करेगा जब सबएरे चंक का आकार 2 की घात हो।
इंसर्शन सॉर्ट का उपयोग करने का लाभ यह है क्योंकि इंसर्शन सॉर्ट छोटे आकार के एरे के लिए ठीक काम करता है।
समय जटिलता -
- बेस्ट केस - Omega(n)
- औसत केस - O(nlogn)
- वर्स्ट केस - O(nlogn)
टिम सॉर्ट के एल्गोरिदम
- आकार 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; // RUN इनिशियलाइज़ करना ताकि चंक्स मिलें
void insertionSort(int arr[], int left, int right) // RUN आकार चंक्स के लिए इंसर्शन सॉर्ट लागू करना{
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) // मर्ज फ़ंक्शन का उपयोग करके आकार 32 के सॉर्टेड चंक्स को एक में मर्ज करना{
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]; // बाएं एरे भरना
for (int i = 0; i < len2; i++)
right[i] = arr[m + 1 + i]; // दाएं एरे भरना
int i = 0;
int j = 0;
int k = l;
while (i < len1 && j < len2) // दोनों एरे लेफ्ट और राइट में पुनरावृति{
if (left[i] <= right[j]) // यदि बाएं में एलिमेंट कम है तो बड़े एरे में पुश करके i बढ़ाएं{
arr[k] = left[i];
i++;
} else {
arr[k] = right[j]; // दाएं एरे में एलिमेंट बड़ा है
j++;
}
k++;
}
while (i < len1) // यह लूप बाएं एरे में शेष एलिमेंट कॉपी करता है{
arr[k] = left[i];
k++;
i++;
}
while (j < len2) // यह लूप दाएं एरे में शेष एलिमेंट कॉपी करता है{
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))); // insertionSort() कॉल करें
for (int s = RUN; s < n; s = 2*s) // आकार RUN (या 32) से मर्जिंग शुरू करें। यह 2*RUN तक जारी रहेगा{
// बाएं सब एरे का प्रारंभिक बिंदु चुनें। हम मर्ज करने जा रहे हैं
// arr[left..left+size-1]
// और arr[left+size, left+2*size-1]
// हर मर्ज के बाद, हम
// left को 2*size से बढ़ाते हैं
for (int left = 0; left < n; left += 2*s){
int mid = left + s - 1; // बाएं सब का अंतिम बिंदु ढूंढें
// mid+1 दाएं सब एरे का प्रारंभिक बिंदु है
int right = min((left + 2*s - 1), (n-1));
merge(arr, left, mid, right); // सब एरे मर्ज करें
// 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;
}
// टिमसॉर्ट एल्गोरिदम लागू करने के लिए मुख्य फ़ंक्शन
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);
// एरे को सॉर्ट करने के लिए timsortAlgo फ़ंक्शन कॉल करना
timSortAlgo(arr, n);
cout<<"After Sorting Array Using TimSort Algorithm- ";
printArray(arr, n); // प्रिंट फ़ंक्शन कॉल करना
return 0;
}