Question

In an effort to balance the distribution (length) of partitions created in the Quicksort algorithm so that worst case performance can be avoided, one can employ randomization, rather than selecting the element at a certain position as the pivot. Use your favorite

programming language to implement the randomized Quicksort algorithm. So, you will need to use the following algorithms to implement it:

RANDOMIZED-PArtitioN (A, p, r) 1 i = RANDOM (p, r) 2 exchange A[r] with A[i] 3 return PARTITION (A, p, r) RANDOMIZED-QUICKSORT (A, p, r) if p <r q RANDOMIZED-PARTITION (A, p, r) RANDOMIZED-QuicK SORT (A, p, q -1 RANDOMIZED-QUICK SORT (A, q + 1,r) 2 3 You may use any random function to implement RANDOM(p,r) in line 1 of the RANDOMIZED- PARTITION algorithm. Please specify in your solution what sort of randomization you use for the RANDOM(p.r) function

Answer 1

Implemented Source Code:-
--------------------------
package com.koothada;
import java.util.Random;
public class Randomized_sort
{
int size;
int Array[];
public Randomized_sort(int size)
{
this.size=size;
Array=new int[size];
}
public void Generate_randomnumbers()
{
Random rand = new Random();
for(int i=0;i<size;i++)
Array[i] = Math.abs(rand.nextInt(100));
}
public void Display()
{
for(int i=0;i<size;i++)
{
System.out.print(Array[i]+" ");
}
}
public void QuickSort(int left, int right)
{
if (right-left<=0)
return;
else
{
Random rand = new Random();
int pivotIndex = left + rand.nextInt(right-left+1);
Exchange(pivotIndex, right);
int pivot = Array[right];
int partition = partition(left, right, pivot);
QuickSort(left, partition - 1);
QuickSort(partition + 1, right);
}
}
public int partition(int left, int right, long pivot)
{
int leftPtr=left-1;
int rightPtr=right;
while (true)
{
while (Array[++leftPtr] < pivot);
while (rightPtr > 0 && Array[--rightPtr] > pivot);
if (leftPtr >= rightPtr)
break;
else
Exchange(leftPtr, rightPtr);
}
Exchange(leftPtr, right);
return leftPtr;
}
public void Exchange(int index1, int index2)
{
int temp = Array[index1];
Array[index1] = Array[index2];
Array[index2] = temp;
}
public static void main(String[] args)
{
Randomized_sort obj=new Randomized_sort(100);//Passing 100 as the size of an Array
System.out.println("---------------------------------------");
System.out.println("*** Randomized Quick Sort **********\n\n");
obj.Generate_randomnumbers();
System.out.println("\nBefore Sorting the Array Elements are:");
obj.Display();
obj.QuickSort(0, obj.size-1);
System.out.println("\n---------------------------------------");
System.out.println("\nAfter Performing Randomized Quick Sort");
obj.Display();
}
}

Sample Output:-

Randomized Quick Sort***** Before Sorting the Array Elements are: 5 84 62 94 71 83 76 22 75 55 68 52 38 73 33 43 88 86 24 31 54 68 86 91 75 35 33 19 50 94 14 89 64 21 99 17 79 32 17 13 68 98 16 76 97 62 50 15 55 71 14 58 63 98 51 14 92 18 66 51 94 82 89 17 62 2 96 40 23 64 42 21 19 13 94 58 78 41 92 97 13 97 19 4 79 27 68 60 23 79 89 31 65 76 93 34 34 15 30 45 After Performing Randomized Quick Sort 245 13 13 13 14 14 14 15 15 16 17 17 17 18 19 19 19 21 21 22 23 23 24 27 30 31 31 32 33 33 34 34 35 38 40 41 42 43 45 50 50 51 51 52 54 55 55 58 58 60 62 62 62 63 64 64 65 66 68 68 68 68 71 71 73 75 75 76 76 76 78 79 79 79 82 83 84 86 86 88 89 89 89 91 92 92 93 94 94 94 94 96 97 97 97 98 98 99 Using random pivoting we improve the expected or average time complexity to O (N log N). The Worst Case complexity is still O ( N^2 ) >In worst case, each partition divides array such that one side has n/4 elements and other side has 3n/4 elements. The worst case height of recursion tree is Log 3/4 n which is O(Log n) >Instead of always using A[r] as the pivot, we will select a randomly chosen element from the subarray A[p..r We do so by first exchanging element A[r] with an element chosen at random from A[p..r] -> ->By randomly sampling the range p...,r, we ensure that the pivot element x-A[r] is equally likely to be any of the r?p+1 elements in the subarray. >Because we randomly choose the pivot element, well balanced on average. expect the split of the input array to be reasonably we