Write four versions of Quicksort in Java.

First version: Select the first item of the partition as the pivot. Treat partitions of size one and two as stopping cases.

Second version: Select the first item of the partition as the pivot. Treat a partition of size 100 as a stopping case. Use an insertion sort to finish.

Third version: Select the first item of the partition as the pivot. Treat a partition of size 50 as a stopping case. Use an insertion sort to finish.

Fourth version: Select the median-of-three as the pivot. Treat partitions of size one and two as stopping cases.

I have provided a general Quicksort algorithm below. Please modify this algorithm to satisfy the four versions above. Thank you.

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

/**

* @author program to perform quick sort for the inputs read from a file

*/

public class Quicksort {

/*

* In below methods the data to be sorted is read from the file. Initially the

* data is form of string, the data is read and split using split method from

* String class and parsed to int below its pushed into an array.

*/

public int[] setupArray() {

Scanner s = null;

try {

s = new Scanner(new File("tester.txt"));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

// String is split using split method with space

String[] contents = s.nextLine().split("\\s+");

int[] array = new int[contents.length];

for (int k = 0; k < contents.length; k++) {

array[k] = Integer.parseInt(contents[k]);

}

return array;

}

/**

* @param arr the array to be sorted

* @param lowValue 0 is lower value

* @param highValue array length - 1 is the higher value

* In this method pivot is calculated considering the middle value.

* Pivot can be even considered higher values depends upon us.

* If the array size is 0 the execution will be returned to the caller.

* using pivot elements are sorted in left side elements lesser than pivot

* and in right side elements greater than pivot. Recursive operation is

* done on the two sub arrays.

*/

public void doQuickSort(int[] arr, int lowValue, int highValue) {

// check for array which has empty or null elements

if (arr == null || arr.length == 0) {

return;

}

//calculate the pivot element from middle of the array

int middle = lowValue + (highValue - lowValue) / 2;

int pivot = arr[middle];

// make left < pivot and right > pivot

int i = lowValue, j = highValue;

while (i <= j) {

// Perform the below until the values on left side array are lower than the pivot

while (arr[i] < pivot) {

i++;

}

// Perform the below until the values on left side array are higher than the pivot

while (arr[j] > pivot) {

j--;

}

// Check the values on both sides of array and check whether they need swapping

// Once the swapping done move the pointer/iterator in both lists

if (i <= j) {

exchangeElements(arr, i, j);

i++;

j--;

}

}

//recursive operation is done on the two sub arrays

if (lowValue < j) {

doQuickSort(arr, lowValue, j);

}

if (highValue > i) {

doQuickSort(arr, i, highValue);

}

}

/**

* @param array the array to be sorted

* @param x first value (may be larger/higher value)

* @param y second value (may be larger/higher value)

*/

public void exchangeElements(int array[], int x, int y) {

int temp = array[x];

array[x] = array[y];

array[y] = temp;

}

/**

* @param args

* used to invoke main method from JVM program execution starts here

*/

public static void main(String[] args) {

Quicksort quickSort = new Quicksort();

int[] dataToSort = quickSort.setupArray();

quickSort.doQuickSort(dataToSort, 0, dataToSort.length - 1);

//Once the elements are sorted, the sorted elements are displayed using for loop.

for(int element : dataToSort) {

System.out.print(element+" ");

}

}

}