C++ Program to Implement Quick Sort with Given Complexity Constraint

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: