Randomized Quick sort

“Randomized quick sort uses random partition method we discussed. We just select a random pivot in an array. The advantage we get is that we can reduce the worst case performance of quick sort!! But still, this optimization is expected!!”

Introduction

   As we have seen a lot about this already, we can directly jump into Randomized quick sort

Concept

  Just select a random pivot element in the partition algorithm.

Code

int random_partition(int* arr, int start, int end)

{

    srand(time(NULL));

    int pivotIdx = start + rand() % (end-start+1);

    int pivot = arr[pivotIdx];

    swap(arr[pivotIdx], arr[end]); // move pivot element to the end

    pivotIdx = end;

    int i = start -1;

    for(int 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 random_quick_sort(int* arr, int start, int end)

{

    if(start < end) {

        int mid = random_partition(arr, start, end);

        random_quick_sort(arr, start, mid-1);

        random_quick_sort(arr, mid+1, end);

    }

}

void main()

{

    int A[] = {2,5,7,1,10,8,9};

    random_quick_sort(A, 0,6);

}

• pivot Index must be start + rand() %(end-start+1).. We do a recursive algorithm with different start and end.. :) so be careful about the formula for pivotIndex
• We need to add start to the rand() % end because we need to get near the size of the array
• start->mid-1 and mid+1->end.. is enough for quick sort.. NOTE: we always get the pivot element in right position at every iteration
• There is an alternate way of partitioning given at many other places.. Not a CLRS way!! :) We will see that as well in the next article..!! :D