random quick sort Algorithm
Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved. develop by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a normally used algorithm for sorting. Robert Sedgewick's Ph.D. thesis in 1975 is considered a milestone in the survey of Quicksort where he resolved many open problems associated to the analysis of various pivot choice schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps.
Jon Bentley and Doug McIlroy integrated various improvements for purpose in programming library, including a technique to deal with equal components and a pivot scheme known as pseudomedian of nine, where a sample of nine components is divided into groups of three and then the median of the three medians from three groups is choose. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library's sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy.
/*
Randomised quick sort implementation in C language.
In normal quick sort, pivot chosen to partition is either the first or the last element of the array.
This can take time O(n*n) to sort in the worst case.
Now in randomised quick sort, pivot is randomly chosen and then recursively sort the left and right sub-arrays.
The expected running time of the algorithm is O(nlog(n)).
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int getBig(int a[], int i, int right, int pivot)
{
for(int k = i; k <= right; k++)
{
if (a[k] > pivot)
return k;
}
return right+1;
}
int getSmall(int a[], int j, int left, int pivot)
{
for(int k = j; k >= left; k--)
{
if (a[k] < pivot)
return k;
}
return -1;
}
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void random_quick(int a[], int left, int right)
{
if (left>=right)
return;
int index = left + (rand()%(right-left)), i = left, j = right;
int pivot_index = index;
int pivot = a[index];
// storing index of element greater than pivot
i = getBig(a, i, right, pivot);
// storing index of element smaller than pivot
j = getSmall(a, j, left, pivot);
while(i <= j)
{
swap(&a[i], &a[j]);
i = getBig(a, i, right, pivot);
j = getSmall(a, j, left, pivot);
}
// after separating the smaller and greater elements, there are 3 cases possible
if(pivot_index>j && pivot_index>i)
{
// case 1. When the pivot element index is greater than both i and j
swap(&a[i], &a[pivot_index]);
random_quick(a, left, i-1);
random_quick(a, i+1, right);
}
else if (pivot_index<j && pivot_index<i)
{
// case 2. When the pivot element index is smaller than both i and j
swap(&a[j], &a[pivot_index]);
random_quick(a, left, j-1);
random_quick(a, j+1, right);
}
else
{
// the pivot element is at its origin position.
random_quick(a, left, pivot_index-1);
random_quick(a, pivot_index+1, right);
}
}
int main()
{
srand(time(0));
int num;
scanf("%d", &num);
int arr[num];
for(int i = 0; i < num; i++)
{
scanf("%d", &arr[i]);
}
random_quick(arr, 0, num-1);
for(int i = 0; i < num; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
