top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

QuickSort and Randomized Quicksort

+1 vote
335 views

I want to know the usage of QuickSort and randomized QuickSort.
Please help me when to use what?

posted Jul 9, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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]);
}
answer Jul 9, 2014 by Salil Agrawal
Similar Questions
0 votes

Are there any benefits from adding a randomized value to CCA Validity-Time in order to reduce reporting storm to PCEF for voice calls. I think there is for non - duration grants - i.e data since number of data sessions are larger than voice calls.

...