কুইক সার্ট ডিভাইড-এন্ড-কনকারের উপর ভিত্তি করে। এই অ্যালগরিদমের গড় সময় জটিলতা O(n log n) কিন্তু বর্জ্য কেস জটিলতা O(n²)। বর্জ্য কেসের সম্ভাবনা কমাতে এখানে কুইক সার্ট র্যান্ডমাইজেশন ব্যবহার করে বাস্তবায়ন করা হয়েছে।
অ্যালগরিদম
partition(int a[], int l, int h)
শুরু pivot = h Index = l start = l এবং end = h যখন start < end করুন যখন a[start] <= pivot এবং start < end করুন start = start + 1 শেষ যখন a[end] > pivot করুন end = end – 1 শেষ যদি start < end হয় তবে a[start] কে a[end]-এর সাথে বদলান শেষ a[low] = a[end] a[end] = pivot end ফেরত দিন শেষ
RandomPivotPartition(int a[], int l, int h)
শুরু n = rand() pivot = l + n % (h - l + 1); a[h] কে a[pivot]-এর সাথে বদলান Partition(a, l, h) ফেরত দিন শেষ
QuickSort(int a[], int l, int h)
শুরু int pindex; যদি (l < h) pindex = RandomPivotPartition(a, l, h) QuickSort(a, l, pindex - 1) QuickSort(a, pindex + 1, h) 0 ফেরত দিন শেষ
উদাহরণ কোড
#include <iostream>
#include <cstdlib>
using namespace std;
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for (i = l; i < h; i++) {
if (a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n % (h - l + 1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
int pindex;
if (l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex - 1);
QuickSort(a, pindex + 1, h);
}
return 0;
}
int main() {
int n, i;
cout << "\nসর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: ";
cin >> n;
int arr[n];
for (i = 0; i < n; i++) {
cout << "এলিমেন্ট " << i + 1 << ": ";
cin >> arr[i];
}
QuickSort(arr, 0, n - 1);
cout << "\nসর্টেড ডাটা ";
for (i = 0; i < n; i++)
cout << "->" << arr[i];
return 0;
}
আউটপুট
সর্ট করার ডাটা উপাদানের সংখ্যা লিখুন: 4 এলিমেন্ট 1: 3 এলিমেন্ট 2: 4 এলিমেন্ট 3: 7 এলিমেন্ট 4: 6 সর্টেড ডাটা ->3->4->6->7
