স্টুগ সার্ট প্রদত্ত ডাটা সর্ট করতে ব্যবহৃত হয়। এটি একটি রিকারসিভ সর্টিং অ্যালগরিদম। স্টুগ সার্ট অ্যারেকে দুটি ওভারল্যাপিং অংশে ভাগ করে, প্রতিটি 2/3 এবং তিন ধাপে সর্ট করে: প্রথমে I, তারপর II এবং আবার I भाग। এই অ্যালগরিদমের বর্জ্য কেস সময় জটিলতা O(n^2.7095)।
অ্যালগরিদম
শুরু ডাটা ইনপুট নিন। StoogeSort() ফাংশন কল করুন 'a' ডাটা অ্যারে এবং 'n' মানগুলির সংখ্যার সাথে আর্গুমেন্ট হিসেবে। রিকারসিভ পদ্ধতিতে সর্টিং বাস্তবায়ন করুন। অ্যারেকে প্রথম 2/3 উপাদান হিসেবে পার্ট I এবং শেষ 2/3 হিসেবে পার্ট II-এ ভাগ করুন। তারপর প্রথম, দ্বিতীয় এবং আবার প্রথম পার্টকে StoogeSort()-এ পাঠান। যদি দৈর্ঘ্য আরও ভাঙা না যায় তবে শুরু এবং শেষে উপাদান বদলান যদি a[end] < a[start] হয়। main-এ ফেরত যান এবং ফলাফল প্রদর্শন করুন। শেষ।
উদাহরণ কোড
#include <iostream>
using namespace std;
void StoogeSort(int a[], int start, int end) {
int temp;
if (end - start + 1 > 2) {
temp = (end - start + 1) / 3;
StoogeSort(a, start, end - temp);
StoogeSort(a, start + temp, end);
StoogeSort(a, start, end - temp);
}
if (a[end] < a[start]) {
temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}
int main() {
int m, i;
cout << "\nসর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: ";
cin >> m;
int arr[m];
for (i = 0; i < m; i++) {
cout << "এলিমেন্ট " << i + 1 << ": ";
cin >> arr[i];
}
StoogeSort(arr, 0, m - 1);
cout << "\nসর্টেড ডাটا ";
for (i = 0; i < m; i++)
cout << "->" << arr[i];
return 0;
}
আউটপুট
সর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: 4 এলিমেন্ট 1: 6 এলিমেন্ট 2: 7 এলিমেন্ট 3: 3 এলিমেন্ট 4: 2 সর্টেড ডাটা ->2->3->6->7
