Question: /** * Implements various sorting algorithms. * * @author (your name), Acuna, Sedgewick * @verison (version) */ public class BurgessSorting { /** * Entry point
/** * 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help