Chương trình C ++ để triển khai sắp xếp nhanh với ràng buộc về độ phức tạp

Sắp xếp nhanh dựa trên chia để trị. Độ phức tạp thời gian trung bình của thuật toán này là O (n * log (n)) nhưng độ phức tạp trong trường hợp xấu nhất là O (n ^ 2). Để giảm nguy cơ xảy ra trường hợp xấu nhất, Quicksort được thực hiện bằng cách sử dụng ngẫu nhiên.

Thuật toán

phân vùng (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

Mã mẫu

#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;
}

Đầu ra

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