টিমসর্ট হল একটি স্থিতিশীল সাজানোর অ্যালগরিদম যা মার্জ সর্ট এবং ইনসার্টেশন সাজানোর ধারণা ব্যবহার করে। এটিকে সন্নিবেশ এবং মার্জ সাজানোর একটি হাইব্রিড অ্যালগরিদমও বলা যেতে পারে। এটি জাভা, পাইথন, সি এবং সি++ ইনবিল্ট সর্ট অ্যালগরিদমে ব্যাপকভাবে ব্যবহৃত হয়। এই অ্যালগরিদমের পিছনে ধারণা হল সন্নিবেশ সাজানোর ব্যবহার করে ছোট খণ্ডগুলিকে সাজানো এবং তারপর মার্জ সর্ট অ্যালগরিদমের মার্জ ফাংশন ব্যবহার করে সমস্ত বড় খণ্ডগুলিকে একত্রিত করা৷
কাজ করছে
এই অ্যালগরিদমে, অ্যারেটি ছোট ছোট অংশে বিভক্ত। খণ্ডগুলো RUN নামে পরিচিত। প্রতিটি RUN নেওয়া হয় এবং সন্নিবেশ সাজানোর কৌশল ব্যবহার করে সাজানো হয়। সমস্ত RUN সাজানোর পরে এইগুলি মার্জ ফাংশন ব্যবহার করে মার্জ করা হয়।
এমন একটি কেস হতে পারে যেখানে অ্যারের আকার RUN এর চেয়ে কম হতে পারে। এই ধরনের ক্ষেত্রে, সন্নিবেশ সাজানোর কৌশল দ্বারা অ্যারে সাজানো হয়। সাধারণত, RUN খণ্ডটি অ্যারের আকারের উপর নির্ভর করে 32 থেকে 64 পর্যন্ত পরিবর্তিত হয়। একত্রীকরণ ফাংশন শুধুমাত্র তখনই একত্রিত হবে যদি সাবারে খণ্ডের ক্ষমতার আকার 2 থাকে।
সন্নিবেশ বাছাই ব্যবহার করার সুবিধা হল কারণ সন্নিবেশ বাছাই ছোট আকারের অ্যারের জন্য ভাল কাজ করে৷
সময় জটিলতা −
-
সেরা কেস - ওমেগা(এন)
-
গড় কেস - O(nlogn)
-
সবচেয়ে খারাপ ক্ষেত্রে - O(nlogn)
টিম সাজানোর অ্যালগরিদম
-
32 এর আকারের সাথে একটি RUN শুরু করুন।
-
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;
} 