Program To Determine If the Characters Are a Part of The Hawaiian Alphabet in Python Assignment Solution.
- Instructions
- Requirements and Specifications
Instructions
Objective
Write a java homework program to implement various sorting techniques using Java programming language.
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;
}
}
Similar Samples
Explore our comprehensive collection of programming samples tailored to sharpen your skills and expand your knowledge. From basic algorithms to advanced data structures, our curated samples cover a wide range of languages and topics, providing invaluable resources for students and professionals alike. Dive in and elevate your understanding of programming concepts today!
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java