/** * Implements various sorting algorithms. * * @author (your name), Acuna, Sedgewick * @verison (version) */

public class BurgessSorting { /** * Entry point for sample output. * * @param args the command line arguments */ public static void main(String[] args) { //Q1 String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; quicksortmid(a); assert isSorted(a); //requires assertions enabled. show(a); //Q2 String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; mergesort(b); assert isSorted(b); show(b); } public static void quicksortmid(Comparable[] a) { //TODO: implement this. } public static void mergesort(Comparable[] a) { //TODO: implement this. } /** * Displays contents of array, space separated. * @author Sedgewick * @param a Array to display. */ private static void show(Comparable[] a) { for (Comparable a1 : a) System.out.print(a1 + " ");

System.out.println(); } /** * Checks if array is in sorted order. * @author Sedgewick * @param a Array to be checked. * @return Returns true if array is sorted. */ public static boolean isSorted(Comparable[] a) { for (int i = 1; i

For reference if helpful:

import java.util.Arrays;

/**

* Sorting demonstrates sorting and searching on an array

* of objects.

*

* @author Lewis and Chase

* @version 4.0

*/

public class Sorting

{

/**

* Sorts the specified array of integers using the selection

* sort algorithm.

*

* @param data the array to be sorted

*/

public static >

void selectionSort(T[] data)

{

int min;

T temp;

for (int index = 0; index

{

min = index;

for (int scan = index+1; scan

if (data[scan].compareTo(data[min])

min = scan;

swap(data, min, index);

}

}

/**

* Swaps to elements in an array. Used by various sorting algorithms.

*

* @param data the array in which the elements are swapped

* @param index1 the index of the first element to be swapped

* @param index2 the index of the second element to be swapped

*/

private static >

void swap(T[] data, int index1, int index2)

{

T temp = data[index1];

data[index1] = data[index2];

data[index2] = temp;

}

/**

* Sorts the specified array of objects using an insertion

* sort algorithm.

*

* @param data the array to be sorted

*/

public static >

void insertionSort(T[] data)

{

for (int index = 1; index

{

T key = data[index];

int position = index;

// shift larger values to the right

while (position > 0 && data[position-1].compareTo(key) > 0)

{

data[position] = data[position-1];

position--;

}

data[position] = key;

}

}

/**

* Sorts the specified array of objects using a bubble sort

* algorithm.

*

* @param data the array to be sorted

*/

public static >

void bubbleSort(T[] data)

{

int position, scan;

T temp;

for (position = data.length - 1; position >= 0; position--)

{

for (scan = 0; scan

{

if (data[scan].compareTo(data[scan+1]) > 0)

swap(data, scan, scan + 1);

}

}

}

/**

* Sorts the specified array of objects using the merge sort

* algorithm.

*

* @param data the array to be sorted

*/

public static >

void mergeSort(T[] data)

{

mergeSort(data, 0, data.length - 1);

}

/**

* Recursively sorts a range of objects in the specified array using the

* merge sort algorithm.

*

* @param data the array to be sorted

* @param min the index of the first element

* @param max the index of the last element

*/

private static >

void mergeSort(T[] data, int min, int max)

{

if (min

{

int mid = (min + max) / 2;

mergeSort(data, min, mid);

mergeSort(data, mid+1, max);

merge(data, min, mid, max);

}

}

/**

* Merges two sorted subarrays of the specified array.

*

* @param data the array to be sorted

* @param first the beginning index of the first subarray

* @param mid the ending index fo the first subarray

* @param last the ending index of the second subarray

*/

@SuppressWarnings("unchecked")

private static >

void merge(T[] data, int first, int mid, int last)

{

T[] temp = (T[])(new Comparable[data.length]);

int first1 = first, last1 = mid; // endpoints of first subarray

int first2 = mid+1, last2 = last; // endpoints of second subarray

int index = first1; // next index open in temp array

// Copy smaller item from each subarray into temp until one

// of the subarrays is exhausted

while (first1

{

if (data[first1].compareTo(data[first2])

{

temp[index] = data[first1];

first1++;

}

else

{

temp[index] = data[first2];

first2++;

}

index++;

}

// Copy remaining elements from first subarray, if any

while (first1

{

temp[index] = data[first1];

first1++;

index++;

}

// Copy remaining elements from second subarray, if any

while (first2

{

temp[index] = data[first2];

first2++;

index++;

}

// Copy merged data into original array

for (index = first; index

data[index] = temp[index];

}

/**

* Sorts the specified array of objects using the quick sort algorithm.

*

* @param data the array to be sorted

*/

public static >

void quickSort(T[] data)

{

quickSort(data, 0, data.length - 1);

}

/**

* Recursively sorts a range of objects in the specified array using the

* quick sort algorithm.

*

* @param data the array to be sorted

* @param min the minimum index in the range to be sorted

* @param max the maximum index in the range to be sorted

*/

private static >

void quickSort(T[] data, int min, int max)

{

if (min

{

// create partitions

int indexofpartition = partition(data, min, max);

// sort the left partition (lower values)

quickSort(data, min, indexofpartition - 1);

// sort the right partition (higher values)

quickSort(data, indexofpartition + 1, max);

}

}

/**

* Used by the quick sort algorithm to find the partition.

*

* @param data the array to be sorted

* @param min the minimum index in the range to be sorted

* @param max the maximum index in the range to be sorted

*/

private static >

int partition(T[] data, int min, int max)

{

T partitionelement;

int left, right;

int middle = (min + max) / 2;

// use the middle data value as the partition element

partitionelement = data[middle];

// move it out of the way for now

swap(data, middle, min);

left = min;

right = max;

while (left

{

// search for an element that is > the partition element

while (left

left++;

// search for an element that is

while (data[right].compareTo(partitionelement) > 0)

right--;

// swap the elements

if (left

swap(data, left, right);

}

// move the partition element into place

swap(data, min, right);

return right;

}

}

2 Requir ements [35 points In this programming project you practice the implementation of sorting algorithms. Download the attached base file for a starting place; includes some very simple testing code. You may modify the base file. However, please retain the signatures of the two stub methods and make sure you keep all of your code in the file. Also attached is Sorting.java, which includes the textbook's sorting algorithm implementations or reter ence LC PP 9.4 modified]: Modify the quick sort method to choose the partition element using the middle of-three technique described in the chapter. 10 points Reimplement the mergesort algorithm to pass only arrays as parameters. This should include a helper method, public static Comparablell mergesort(Comparablell a), and a merge method, public static Comparablell merge(Comparablell a, Comparablell b). Do not use global variables. (This approach is slower than the mergesort from the book. The goal is to better understand th egesot concept.) 15 points