প্রদত্ত জটিলতা সীমাবদ্ধতার সাথে দ্রুত সাজানোর জন্য C++ প্রোগ্রাম

দ্রুত বাছাই বিভক্ত এবং জয়ের উপর ভিত্তি করে। এই অ্যালগরিদমের গড় সময় জটিলতা হল O(n*log(n)) কিন্তু সবচেয়ে খারাপ ক্ষেত্রে জটিলতা হল O(n^2)। সবচেয়ে খারাপ পরিস্থিতির সম্ভাবনা কমাতে এখানে Quicksort র্যান্ডমাইজেশন ব্যবহার করে প্রয়োগ করা হয়েছে।

অ্যালগরিদম

পার্টিশন(int a[], int l,int h)

Begin
   pivot = h
   Index = l
   start = l and end = h
   while start < end do
      while a[start] <= pivot AND start < end do
         start = start +1
      done
      while a[end] > pivot do
         end = end – 1
      done
      if start < end then
         swap a[start] with a[end]
      done
      a[low] = a[end]
      a[end] = pivot
   return end
End

RandomPivotPartition(int a[], int l, int h)

Begin
   n = rand()
   pivot = l + n%(h-l+1);
   Swap a[h] with a[pivot]
   return Partition(a, l, h)
End

QuickSort(int a[], int l, int h)

Begin
   int pindex;
   If (l<h)
      pindex = RandomPivotPartition(a, l, h)
      QuickSort(a, l, pindex-1)
      QuickSort(a, pindex+1, h)
   return 0
End

উদাহরণ কোড

#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<<"\nEnter the number of data element to be sorted: ";
   cin>>n;
   int arr[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   QuickSort(arr, 0, n-1);
   cout<<"\nSorted Data ";
   for (i = 0; i < n; i++)
      cout<<"->"<<arr[i];
   return 0;
}

আউটপুট

Enter the number of data element to be sorted: 4 Enter element 1: 3
Enter element 2: 4
Enter element 3: 7
Enter element 4: 6
Sorted Data ->3->4->6->7