+1 (315) 557-6473 

Program To Implement Various Sorting Techniques Using Java Programming Language Assignment Solution.


Instructions

Objective
Write a java homework program to implement various sorting techniques using Java programming language.

Requirements and Specifications

Implement various sorting techniques in Java programming language

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

  *

  *

      *

  1. Check for single array
  2.   *

  3. Divide array in half
  4.   *

  5. Merge sort first half
  6.   *

  7. Merge sort second half
  8.   *

  9. Combine halves
  10.   *

  *

  * @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:

  *

      *

  1. Choose a pivot (store in first bucket for convenience)
  2.   *

  3. 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

  4.   *

  5. put the pivot back between upper and lower group
  6.   *

  7. sort left side
  8.   *

  9. sort right side
  10.   *

  * (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;

 }

}