Instructions
Requirements and Specifications
Source Code
INSERTION SORT
package sortEvaluations;
/**
* This is an implementation of the Insertion Sort Routine
*/
public class InsertionSort> implements Sorter {
/**
* {@inheritDoc}
*/
@Override
public String nameOfSort() {
return "Insertion Sort";
}
/**
* {@inheritDoc}
*
*
* This will have no affect on insertion sort itself.
*/
@Override
public void setConstant(double constant) {
// No affect on Insertion Sort
}
/**
* {@inheritDoc}
*
* Sort the array using the insertion sort algorithm
*/
@Override
public void sort(Type[] array) {
int i = 1;
while (i < array.length) {
int j = i;
while (j > 0 && array[j-1].compareTo(array[j]) > 0) {
Sorter.swap(array, j, j-1);
j--;
}
i++;
}
}
/**
* Insertion Sort.
*
* Write an inplace insertion sort that works on the VIRTUAL array defined by the actual array from
* [start --> end].
*
* This is placed here as a static method so that it can be used by Merge Sort and Quick Sort for their
* cutoff enhancement. You can also simply call it in the sort method above as well...
*
* @param - a comparable object
* @param array - The array to sort
* @param start - the start of the (sub) array to sort
* @param end - the end of the (sub) array to sort
*/
public static > void sort(Type[] array, int start, int end) {
// int i = start + 1;
// while (i < end + 1) {
// int j = i;
// while (j > start && array[j-1].compareTo(array[j]) > 0) {
// sortEvaluations.Sorter.swap(array, j, j-1);
// j--;
// }
// i++;
// }
}
/**
* {@inheritDoc}
*/
@Override
public ComplexityClass getExpectedComplexityClass() {
return ComplexityClass.N_SQUARED;
}
}
MERGE SORT
package sortEvaluations;
/**
* This is an implementation of the Merge Sort Routine
*/
public class MergeSort> implements Sorter {
/**
* Have a value for switching over to insertion sort. Should be changed
* by the setConstant method.
*/
double cutOff = 7;
/**
* {@inheritDoc}
*/
@Override
public String nameOfSort() {
return "Merge Sort using a cutoff " + this.cutOff;
}
/**
* Merge sort
*
*
*
- Check for single array
*
- Divide array in half
*
- Merge sort first half
*
- Merge sort second half
*
- Combine halves
*
*
* @param array - The array to sort
* @param auxillary - The auxillary array to help copy values
* @param low - the low index of the (sub) array
* @param high - the high index of the (sub) array
*/
private void mergeSort(Type[] array, Type[] auxillary, int low, int high) {
if (low >= high) {
return;
}
int middle = (low + high) / 2;
mergeSort(array, auxillary, low, middle);
mergeSort(array, auxillary, middle+1, high);
merge(array, auxillary, low, middle, high);
}
/**
* Merge the sub arrays (or the left and right arrays). Use the
* auxillary array for extra space to help copy values or for
* "scratch space"
*
* @param array - The array to sort
* @param auxillary - The auxillary array to help copy values
* @param low - the low index of the "lower" or "left" array
* @param mid - the mid index of the two sub arrays
* @param high - the high index of the "upper" or "right" array
*/
private void merge(Type[] array, Type[] auxillary, int low, int mid, int high) {
if (high + 1 - low >= 0) System.arraycopy(array, low, auxillary, low, high + 1 - low);
int i = low;
int j = mid + 1;
for (int k = low; k <= high; k++) {
if (i > mid) {
array[k] = auxillary[j];
j++;
} else if (j > high) {
array[k] = auxillary[i];
i++;
} else if (auxillary[i].compareTo(auxillary[j]) <= 0) {
array[k] = auxillary[i];
i++;
} else {
array[k] = auxillary[j];
j++;
}
}
}
/**
* {@inheritDoc}
*
* Changes the cutoff for when to use insertion sort.
*/
public void setConstant(double cutoff) {
this.cutOff = cutoff;
}
/**
* {@inheritDoc}
*
* Sort the array using the merge sort algorithm
*/
@Override
public void sort(Type[] array) {
// These tricky lines of code is creating a new generic array for you...
@SuppressWarnings("unchecked")
Type[] auxillary = (Type[]) java.lang.reflect.Array.newInstance(array.getClass().getComponentType(),
array.length);
mergeSort(array, auxillary, 0, array.length - 1);
}
/**
* {@inheritDoc}
*/
@Override
public ComplexityClass getExpectedComplexityClass() {
return ComplexityClass.N_LOG_N;
}
}
QUICK SORT
package sortEvaluations;
import java.util.Random;
/**
* This code is an abstract base class for all versions of quicksort.
*
* The children classes will implement the toString and getPivot methods.
*
* Instrument it to allow the changing of the Insertion Sort Switch over.
*/
public abstract class QuickSort> implements Sorter {
/**
* Create a field for the insertion sort cutoff level. Should be
* changed by setConstant.
*/
double cutoff = 3;
/**
* Choose a Pivot in the array. The pivot location will be used to swap the
* first value in the array. Each Quick Sort will apply this differently.
*
* @param array - The array to sort
* @param start - the start position in the (sub) array
* @param mid - the mid position in the (sub) array
* @param end - the end position in the (sub) array
* @return - the index of the element to swap
*/
protected abstract int getPivot(Type[] array, int start, int mid, int end);
/**
* Given an array, partition the array such that all the elements lower than or
* equal to the pivot are on the left, all the elements greater than the pivot
* are on the right.
*
* @param array - data data to sort
* @param left - the start index of the sub array (inclusive)
* @param right - the end index of the sub array (inclusive)
*
* @return the location of the pivot
*/
protected int partition(Type[] array, int left, int right) {
int pivotIndex = getPivot(array, left, (left + right)/2, right);
Sorter.swap(array, pivotIndex, right);
Type pivot = array[right];
int i = (left-1);
for (int j = left; j < right; j++) {
if (array[j].compareTo(pivot) < 0 || (array[j].compareTo(pivot) == 0 && new Random().nextBoolean())) {
i++;
Sorter.swap(array, i, j);
}
}
Sorter.swap(array, i+1, right);
return i+1;
}
/**
* The actual Quick Sort on an Array routine.
*
* Algorithm:
*
*
- Choose a pivot (store in first bucket for convenience)
*
- move all elements higher than the pivot to the right side of the array
* move all elements lower than the pivot to the left side of the array
*
- put the pivot back between upper and lower group
*
- sort left side
*
- sort right side
*
* (WARNING: don't sort pivot again)
*
* @param array - data to be sorted
* @param start is the index of the beginning element
* @param end is the index of the last element
*/
private void quickSort(Type[] array, int start, int end) {
if (start < end) {
int partitionIndex = partition(array, start, end);
quickSort(array, start, partitionIndex-1);
quickSort(array, partitionIndex+1, end);
}
}
/**
* {@inheritDoc}
*
* Sort the array using the quick sort algorithm.
*/
public void sort(Type[] array) {
quickSort(array, 0, array.length - 1);
}
/**
* The constant in this case is the insertion sort cutoff level... always
* greater than 3
*/
public void setConstant(double constant) {
this.cutoff = constant;
}
/**
* {@inheritDoc}
*/
@Override
public ComplexityClass getExpectedComplexityClass() {
return ComplexityClass.N_LOG_N;
}
}
SHELL SORT
package sortEvaluations;
/**
* Code inspired by Mark Allen Weiss' code
* this is an implementation of the Shell Sort Routine
*
* This code is provided for you as an example.
*
* @author H. James de St. Germain - Edited by Alex May
* @date Spring 2007
* @edited Fall 2020
*/
public class ShellSort> implements Sorter {
/**
* The choice of "gap" for shell sort. This can be changed by setConstant
*/
double GAP = 2.2;
/**
* {@inheritDoc}
*/
public String nameOfSort() {
return "Shell Sort using a gap of " + this.GAP;
}
/**
* For details on Shell Sort, see the Text or google
*
* @param array the values to sort from small to high
*/
private void shellSort(Type[] array) {
int gap = array.length / 2;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
Type tmp = array[i];
int j = i;
while (j >= gap && tmp.compareTo(array[j - gap]) < 0) {
Sorter.swap(array, j, j - gap);
j -= gap;
}
}
// change the gap value to a smaller value
if (gap == 2) {
gap = 1;
} else {
gap = (int) (gap / this.GAP);
}
}
}
/**
*
* {@inheritDoc}
*
* For Shell Sort, this allows the gap to be changed to test other
* values.
*/
public void setConstant(double cutoff) {
this.GAP = cutoff;
}
/**
* {@inheritDoc}
*
* This will sort the array using Shell Sort.
*/
@Override
public void sort(Type[] array) {
shellSort(array);
}
/**
* {@inheritDoc}
*
* Shell sort is an N_SQUARED algorithm.
*/
@Override
public ComplexityClass getExpectedComplexityClass() {
return ComplexityClass.N_SQUARED;
}
}