Code:
#include iostream
#include cstdlib
using namespace std;
// Swapping two values.
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
int pivot, index, i;
index = low;
pivot = high;
// Getting index of pivot.
for(i=low; i < high; i++)
{
if(a[i] < a[pivot])
{
swap(&a[i], &a[index]);
index++;
}
}
// Swapping value at high and at the index obtained.
swap(&a[pivot], &a[index]);
return index;
}
// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
int pvt, n, temp;
n = rand();
// Randomizing the pivot value in the given subpart of array.
pvt = low + n%(high-low+1);
// Swapping pvt value from high, so pvt value will be taken as pivot while partitioning.
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
// Implementing QuickSort algorithm.
int QuickSort(int a[], int low, int high)
{
int pindex;
if(low < high)
{
// Partitioning array using randomized pivot.
pindex = RandomPivotPartition(a, low, high);
// Recursively implementing QuickSort.
QuickSort(a, low, pindex-1);
QuickSort(a, pindex+1, high);
}
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 "<
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<
return 0;
}
Output:
Case 1: (avg case)
Enter the number of data element to be sorted: 10
Enter element 1: 23
Enter element 2: 9876
Enter element 3: 459
Enter element 4: 650
Enter element 5: 32
Enter element 6: 9
Enter element 7: 4705
Enter element 8: 1
Enter element 9: 17
Enter element 10: 3
Sorted Data ->1->3->9->17->23->32->459->650->4705->9876
More C++ Programs:
