Question

Provide two possible ways to go beyond randomized quick sort to enhance the algorithm to a better running time and implement in Java one of the ways you provide (add few comments to explain your code)

Answer 1

QuickSort picks an element as pivot and partitions the given array around the picked pivot.

There are many different versions of quickSort that pick pivot in different ways.

• Always pick first element as pivot.
• Always pick last element as pivot
• Pick a random element as pivot.
• Pick median as pivot.

==> Algorithm for random pivoting using Lomuto Partitioning

partition(arr[], low, high)
pivot = arr[high]
i = low // place for swapping
for j := low to high – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[high]
return i

partition_r(arr[], low, high)
r = Random Number from low to high
Swap arr[r] and arr[high]
return partition(arr, low, high)

quicksort(arr[], low, high)
if low < high
p = partition_r(arr, low, high)
quicksort(arr, low, p-1)
quicksort(arr, p+1, high)

==> Algorithm for random pivoting using Hoare Partitioning

partition(arr[], low, high)
pivot = arr[lo]
i = low - 1 // Initialize left index
j = high + 1 // Initialize right index

// Find a value in left side greater than pivot
do
i = i + 1
while arr[i] pivot

if i >= j then
return j

swap arr[i] with arr[j]

partition_r(arr[], lo, hi)
r = Random number from low to high
Swap arr[r] and arr[lo]
return partition(arr, low, high)

quicksort(arr[], lo, hi)
if low < high
p = partition_r(arr, low, high)
quicksort(arr, low, p)
quicksort(arr, p+1, high)

Code for random pivoting using Lomuto Partitioning

import java.util.*;
class RandomQsort
{
    // This Function helps in calculating random numbers between low and high
    static void random(int arr[],int low,int high)
    {
        Random rand= new Random();
        int pivot = rand.nextInt(high-low)+low;
        int temp1=arr[pivot];
        arr[pivot]=arr[high];
        arr[high]=temp1;
    }
    // This function takes last element as pivot,
    static int partition(int arr[], int low, int high)
    {
        // pivot is choosen randomly 
        random(arr,low,high);
        int pivot = arr[high];

        int i = (low-1); // index of smaller element 
        for (int j = low; j < high; j++)
        {
            // If current element is smaller than or 
            // equal to pivot 
            if (arr[j] < pivot)
            {
                i++;
                // swap arr[i] and arr[j] 
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap arr[i+1] and arr[high] (or pivot) 
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        return i+1;
    }
    // The main function that implements QuickSort()
    static void sort(int arr[], int low, int high)
    {
        if (low < high)
        { 
            /* pi is partitioning index, arr[pi] is 
            now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
    public static void main(String args[])
    {
        int n;
        Scanner s1= new Scanner(System.in);
        System.out.println("Enter value of n which is size of array : ");
        n=s1.nextInt();
        int arr[]=new int[n];
        System.out.println("Enter Array:");
        for(int i=0;i<n;i++)
        {
            arr[i]=s1.nextInt();
        }
        int j = arr.length;
        sort(arr, 0, j-1);
        System.out.println("Sorted array");
        printArray(arr);
    }
} 

output:

Enter value of n which is size of array :
5
Enter Array:
1 9 7 3 10
Sorted array
1 3 7 9 10

output(SS):

This is output of code: