सी ++ में टिम सॉर्ट एल्गोरिदम

टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है जो मर्ज सॉर्ट और इंसर्शन सॉर्ट के विचार का उपयोग करता है। इसे इंसर्शन और मर्ज सॉर्ट का हाइब्रिड एल्गोरिथम भी कहा जा सकता है। यह जावा, पायथन, सी, और सी ++ इनबिल्ट सॉर्ट एल्गोरिदम में व्यापक रूप से उपयोग किया जाता है। इस एल्गोरिथम के पीछे का विचार है कि सम्मिलन सॉर्ट का उपयोग करके छोटे विखंडू को क्रमबद्ध किया जाए और फिर मर्ज सॉर्ट एल्गोरिथ्म के मर्ज फ़ंक्शन का उपयोग करके सभी बड़े विखंडू को मर्ज किया जाए।

काम कर रहे हैं

इस एल्गोरिथम में, सरणी को छोटे टुकड़ों में विभाजित किया जाता है। भाग को रन के रूप में जाना जाता है। प्रत्येक RUN को इंसर्शन सॉर्ट तकनीक का उपयोग करके लिया और सॉर्ट किया जाता है। सभी RUN को सॉर्ट करने के बाद इन्हें मर्ज फ़ंक्शन का उपयोग करके मर्ज कर दिया जाता है।

ऐसा मामला हो सकता है जहां सरणी का आकार रन से कम हो सकता है। ऐसे मामले में, सरणी को सम्मिलन सॉर्ट तकनीक द्वारा क्रमबद्ध किया जाता है। आमतौर पर, रन खंड सरणी के आकार के आधार पर 32 से 64 तक भिन्न होता है। मर्ज फ़ंक्शन केवल तभी मर्ज होगा जब सबअरे चंक में 2 की शक्तियों का आकार हो।

इंसर्शन सॉर्ट का उपयोग करने का लाभ यह है कि छोटे आकार वाले एरे के लिए इंसर्शन सॉर्ट ठीक काम करता है।

समय की जटिलता -

• बेस्ट केस - ओमेगा(एन)

• औसत मामला - O(nlogn)

• सबसे खराब स्थिति - O(nlogn)

टिम सॉर्ट के एल्गोरिदम

• 32 के आकार के साथ एक रन शुरू करें।

• RUN आकार के टुकड़ों के लिए सम्मिलन क्रम लागू करें।

• एक फ़ंक्शन मर्ज (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;
}