Quicksort worst case performance is o(n^2) when list is already sorted which is same as bubble sort. To avoid worst case performance we use randomized quick sort which uses random partition. See the following code -
swap(int *a, int *b)
{
int c;
c = *a;
*a = *b;
*b = c;
}
int randomPartition(int* arr, int start, int end)
{
int pivotIdx, pivot, i, j;
srand(time(NULL));
pivotIdx = start + rand() % (end-start+1);
pivot = arr[pivotIdx];
swap(&arr[pivotIdx], &arr[end]); // move pivot element to the end
pivotIdx = end;
i = start -1;
for(j=start; j<=end-1; j++)
{
if(arr[j] <= pivot)
{
i = i+1;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[pivotIdx]);
return i+1;
}
void randomQuickSort(int* arr, int start, int end)
{
int mid;
if(start < end) {
mid = randomPartition(arr, start, end);
randomQuickSort(arr, start, mid-1);
randomQuickSort(arr, mid+1, end);
}
}
void main()
{
int A[] = {20,50,70,10,100,80,90};
int i = 0;
randomQuickSort(A, 0,6);
for (i=0;i<7;i++)
printf("%d \n", A[i]);
}