Question

Hi i will give you a thumbs up if you do this problem correctly.

Sorting Analysis

Code and Essay Due: 4/22/2019(Monday)

1. Introduction

And now for something completely different.   Different sorting algorithms are better for different size data sets.   Other sorting algorithms are better for data sets of a specific type – for instance, data that is already ordered. In this assignment you will implement four different sorting algorithms and collect statistics for each of those algorithms while sorting multiple different data sets.

After you have written the code, and have gathered statistics you must write an essay describing your results.   You must include data to support your position.   See section 2.5 for details.

2. Requirements

Create a Java project called SortAnalysis.   Within that project you will have the following classes:

1. Sorter Classes (Total of 4)

In this assignment you must implement four different sort algorithms as four different classes named – BubbleSort, SelectionSort, InsertionSort, and MergeSort. Each of the classes must be in its own .java file.   Each of those four classes must implement a null constructor, and implement the following ISorter interface.

public interface ISorter {

    ISortStats sort(int[] a)

}

The sort method for each of the sorters must implement the sort described by the class name such that the array passed in is sorted from smallest to largest. You may have additional private methods in your sorter classes, but after construction the main Program (see below) must only reference the sorter classes through the single method defined in the ISorter interface. In all cases, the sort method must return a single object that implements the ISortStats interface.   See section 2.2 below.

2. SortStats Class

You must also implement a class named SortStats that implements the following ISortStats interface.

public interface ISortStats {

    String getAlgorithm();

    int    getNumItems();

    int   getNumComparisons();

    int    getNumMoves();

    long   getNumNanoseconds();

}

The SortStats class must not have any public variables and must not have any mutators. All values in a SortStats object are required to be passed into the object and saved via the SortStats constructor.

The SortStats class must also implement a toString() method that returns a string in the following format:

{

    "Algorithm"     : "<algorithm>",

    "NumItems"       : "<numItems>",

    "NumComparisons" : "<numComparisons>",

    "NumMoves"       : "<numMoves>",

    "NumNanoseconds" : "<numNanoseconds>"

}

Where <algorithm> is the name of the class doing the sorting (e.g. BubbleSort, MergeSort, etc.) and   where <numItems> is the number of items being sorted for that particular call to sort, <numComparisons> is the number of times elements are compared to each other (<, >, or ==), <numMoves> is the number of times elements are assigned into the array or a temporary variable – (e.g a typical swap is 3 moves).   <numNanoseconds> is the number of elapsed nanoseconds spent sorting. You can compute the number of nanoseconds by calling the method System.nanoTime() at the beginning and end of your sort method and returning the difference.   The object is then returned to the caller for display – DO NOT display any values in any of the sort methods.

3. Program Class

You must also implement a class called Program.   This class will contain your main method.   From that main method you must test your sorters in two different ways.

In the first set of tests you must vary the size of the test array from 1 to 4096 inclusive, by powers of 2. (Thus there will be 12 different test arrays altogether.) Then within that, you must vary the sorter being used so that you test all sorters against all of the different array sizes.

In the second set of tests the number of elements in the array is fixed at 4096.   But you are varying the way the arrays are initialized.   More specifically, you must vary the order of the arrays in two different ways.   In the first case, the data must be initialized so that the numbers are ordered from largest to smallest prior to sorting.   In the second case, you must initialize the array such that it is already in sorted order (smallest to largest), and then “sort” the already sorted array.

This second set of tests, combined with the first set of tests, ensure that you have data initialized three different ways – random, reverse order and in order.

Within each set of tests you will 1) iterate over the data set sizes / types. 2) iterate over your sorters, 3) sort the current data set with your sorter and capture the results (SortStats), 4) Call Check.isInOrder (see below) to verify that your array is in order, and 5) display the results using the toString() method of the SortStats.

4. Check Class

You must also implement a class named Check.   This class must contain exactly one static method named isInOrder that takes a single integer array as a parameter and returns a boolean indicating whether or not the array is in order (from smallest to largest).

public boolean isInOrder(int[] a)

3. Data Sets

You will test your sort algorithms against multiple data sets (arrays) as described above.   During these tests it is important that each of your different sorters be applied to the exact same data – the exact same values, in the exact same order.   In order to do this, whenever a data set (an array) is generated, it must be saved and set aside.   Before each call to sort, you must make a copy of the input array, and then pass that copy to sort.   This ensures that you always start with the same data for each of the different sorters.

Reverse Order

The easiest way to generate an array in reverse order is to start at some very high number like Integer.MAX_VALUE, and then fill in the array going downward (toward zero) by subtracting some small random number from the prior entry.   For instance, decreasing by a random value between 1 and 4096.   This ensures that the numbers always decrease and never wrap (at least not for data sets of size 4096 or smaller)

In Order

Once you sort an array that started in reverse order, then the array is now in order.   There is no need to create a different array to test the re-sort of a sorted array

Random Order

You can call Collections.shuffle to create a random order array from a preexisting array.

Answer 1

Hello,

The complete code is as below. Let me know if you need any modification.

ISorter.java

public interface ISorter {
   ISortStats sort(int[] a);
}

ISortStats.java

public interface ISortStats {
   String getAlgorithm();
int getNumItems();
int getNumComparisons();
int getNumMoves();
long getNumNanoseconds();
}

SortStats.java

public class SortStats implements ISortStats {
   private String algorithm;       // Name of class doing sorting
   private int numItems;           // Number of items sorted
   private int numComparisons;       // Number of times elements compared to each other
   private int numMoves;           // Number of times elements are assigned into array or temporary variable
   private long numNanoseconds;   // Time taken to sort
  
   public SortStats(String algorithm, int numItems, int numComparisons, int numMoves, long numNanoseconds)
   {
       this.algorithm = algorithm;
       this.numItems = numItems;
       this.numComparisons = numComparisons;
       this.numMoves = numMoves;
       this.numNanoseconds = numNanoseconds;
   }
  
   @Override
   public String getAlgorithm() {
       return algorithm;
   }

   @Override
   public int getNumItems() {
       return numItems;
   }

   @Override
   public int getNumComparisons() {
       return numComparisons;
   }

   @Override
   public int getNumMoves() {
       return numMoves;
   }

   @Override
   public long getNumNanoseconds() {
       return numNanoseconds;
   }
  
   public String toString()
   {
       String output = "\nAlgorithm : \"" + getAlgorithm() + "\""
                       + "\nNumItems : \"" + getNumItems() + "\""
                       + "\nNumComparisons: \"" + getNumComparisons() + "\""
                       + "\nNumMoves : \"" + getNumMoves() + "\""
                       + "\nNumNanoseconds : \"" + getNumNanoseconds() + "\"";
      
       return output;
   }

}

BubbleSort.java

public class BubbleSort implements ISorter {
   private String algorithm;       // Name of class doing sorting
   private int numItems;           // Number of items sorted
   private int numComparisons;       // Number of times elements compared to each other
   private int numMoves;           // Number of times elements are assigned into array or temporary variable
   private long numNanoseconds;   // Time taken to sort
  
   public BubbleSort()
   {
       algorithm = "Bubble Sort";
       numItems = 0;
       numComparisons = 0;
       numMoves = 0;
       numNanoseconds = 0;
   }

   @Override
   public ISortStats sort(int[] a) {
       int n = a.length;
       long start = System.nanoTime();
      
       for(int i = 0; i < n; i++)
       {
           for(int j=1; j < (n-i); j++)
           {
               if(a[j-1] > a[j])
               {
                   int temp = a[j-1];
                   a[j-1] = a[j];
                   a[j] = temp;
      
                   numItems++;           // Count number of items sorted
                   numComparisons++;   // Count number of comparisons
                   numMoves += 3;       // Count number of moves
               }
           }
       }
      
       long end = System.nanoTime();
       numNanoseconds = end - start;   // Calculate sorting time
      
       SortStats stats = new SortStats(algorithm, numItems, numComparisons, numMoves, numNanoseconds);
       return stats;
   }
}

SelectionSort.java

public class SelectionSort implements ISorter {
   private String algorithm;       // Name of class doing sorting
   private int numItems;           // Number of items sorted
   private int numComparisons;       // Number of times elements compared to each other
   private int numMoves;           // Number of times elements are assigned into array or temporary variable
   private long numNanoseconds;   // Time taken to sort
  
   public SelectionSort()
   {
       algorithm = "Selection Sort";
       numItems = 0;
       numComparisons = 0;
       numMoves = 0;
       numNanoseconds = 0;
   }

   @Override
   public ISortStats sort(int[] a) {
       int n = a.length;
       long start = System.nanoTime();
      
       for (int i = 0; i < n-1; i++)
       {
           // Get the minimum element in unsorted array
           int min = i;
           boolean found = false;
          
           for (int j = i+1; j < n; j++)
           {
               if (a[j] < a[min])
               {
                   min = j;
                   found = true;
                   numComparisons++;   // Count number of comparisons
               }
           }
          
           // Swap the found element with first element
           if(found == true)
           {
               int temp = a[min];
               a[min] = a[i];
               a[i] = temp;
               numItems++;       // Count number of items sorted
               numMoves += 3;   // Count number of moves
           }          
}
      
       long end = System.nanoTime();
       numNanoseconds = end - start;   // Calculate sorting time
      
       SortStats stats = new SortStats(algorithm, numItems, numComparisons, numMoves, numNanoseconds);
       return stats;
   }
}

InsertionSort.java

public class InsertionSort implements ISorter {
   private String algorithm;       // Name of class doing sorting
   private int numItems;           // Number of items sorted
   private int numComparisons;       // Number of times elements compared to each other
   private int numMoves;           // Number of times elements are assigned into array or temporary variable
   private long numNanoseconds;   // Time taken to sort
  
   public InsertionSort()
   {
       algorithm = "Insertion Sort";
       numItems = 0;
       numComparisons = 0;
       numMoves = 0;
       numNanoseconds = 0;
   }

   @Override
   public ISortStats sort(int[] a) {
       int n = a.length;
       boolean sorted = false;       // Helper variable to count number of sorted items
       long start = System.nanoTime();
      
       for (int i = 1; i < n; ++i)
       {
           int j = i - 1;
           sorted = false;
          
           // Shift elements that are greater than key to one position ahead of their current position
           while ( j >= 0 && a[j] > a[i])
           {
               a[j + 1] = a[j];
               j = j - 1;
              
               sorted = true;
               numComparisons++;   // Count number of comparisons
               numMoves++;           // Count number of moves
           }
          
           if(sorted == true)
           {
               a[j + 1] = a[i];
               numMoves++;           // Count number of moves
               numItems++;           // Count number of items sorted
           }
       }
      
       long end = System.nanoTime();
       numNanoseconds = end - start;   // Calculate sorting time
      
       SortStats stats = new SortStats(algorithm, numItems, numComparisons, numMoves, numNanoseconds);
       return stats;
   }
}

MergeSort.java

public class MergeSort implements ISorter{
   private String algorithm;       // Name of class doing sorting
   private int numItems;           // Number of items sorted
   private int numComparisons;       // Number of times elements compared to each other
   private int numMoves;           // Number of times elements are assigned into array or temporary variable
   private long numNanoseconds;   // Time taken to sort
  
   public MergeSort()
   {
       algorithm = "Merge Sort";
       numItems = 0;
       numComparisons = 0;
       numMoves = 0;
       numNanoseconds = 0;
   }
  
   // Method to split the array into sub array
   private int[] getSubArray(int[] a, int n1, int n2)
   {
       int[] subArr = new int [n1];
       for (int i=0; i<n1; ++i)
       {
           subArr[i] = a[n2 + i];
           numMoves++;       // Count number of moves
       }
      
       return subArr;
   }
  
   void merge(int a[], int min, int mid, int max)
   {
       // Find sizes of two subarrays to be merged
       int n1 = mid - min + 1;
       int n2 = max - mid;
      
       // Create temporary arrays
       int[] left = getSubArray(a, n1, min);
       int[] right = getSubArray(a, n2, mid + 1);
      
// Merge the temporary arrays
       // Initial indexes of subarrays and final array
       int i = 0, j = 0, k = min;
      
       while (i < n1 && j < n2)
       {
           if (left[i] <= right[j])
               a[k] = left[i++];
           else
               a[k] = right[j++];
           k++;
          
           numItems++;           // Count number of items sorted
           numComparisons++;   // Count number of comparisons
           numMoves++;           // Count number of moves
       }
      
       // Copy remaining elements of left[] if any
       while (i < n1)
       {
           a[k++] = left[i++];
           numMoves++;       // Count number of moves
       }
      
       // Copy remaining elements of right[] if any
       while (j < n2)
       {
           a[k++] = right[j++];
           numMoves++;       // Count number of moves
       }
   }
  
   private void mergeSort(int[] a, int min, int max)
   {
       if(min < max)
       {
           // Find the middle point
           int mid = (min+max)/2;

// Sort first and second halves
mergeSort(a, min, mid);
mergeSort(a , mid+1, max);
  
// Merge the sorted halves
merge(a, min, mid, max);
       }
   }

   @Override
   public ISortStats sort(int[] a) {
       numItems = a.length;
      
       long start = System.nanoTime();
       mergeSort(a, 0, numItems-1);
      
       long end = System.nanoTime();
       numNanoseconds = end - start;   // Calculate sorting time
      
       SortStats stats = new SortStats(algorithm, numItems, numComparisons, numMoves, numNanoseconds);
       return stats;
   }
}

Check.java

public class Check {
   static public boolean isInOrder(int[] a)
   {
       // Check whether given array is in ascending order
       for(int i=0; i<a.length-1; i++)
           // Return false if current item is greater than next item
           if(a[i] > a[i+1])
               return false;
      
       // Items are in order, hence return true
       return true;
   }
}

Program.java

import java.util.Random;

public class Program {
  
   // Method executes all the sorters classes and display the sort status
   public static void executeSorters(int[] a)
   {
       ISortStats stats;
       ISorter sorter[] = new ISorter[4];
      
       // Create instance of sorter classes
       sorter[0] = new BubbleSort();
       sorter[1] = new SelectionSort();
       sorter[2] = new InsertionSort();
       sorter[3] = new MergeSort();
      
       // Sort and display sort status
       System.out.println("\n\n\tARRAY SIZE: " + a.length);
       for(int i = 0; i < sorter.length; i++)
       {
           int temp[] = a.clone();
           stats = sorter[i].sort(temp);
          
           if(Check.isInOrder(temp))
               System.out.println(stats);
       }
   }
  
   // First Set of Data: Total 12 array test
   public static void testCase1()
   {
       int max = 1;
      
       // Generate random numbers
       int[] a = new int[4096];
       Random rand = new Random();
       for(int i = 0; i < a.length; i++)
           a[i] = rand.nextInt();
      
       while(max < a.length)
       {
           max = max * 2;   // Powers of 2
          
           int[] subArray = new int[max];
           System.arraycopy(a, 0, subArray, 0, max);   // Create subarray for the max length
          
           executeSorters(subArray);
       }
   }
  
   // Second Set of Data: Execute sorting for in-order and unsorted array
   public static void testCase2()
   {
       int[] a = new int[4096];
       int digit = a.length;
      
       /* Case 1: Numbers in descending order - Largest to Smallest */
       // Initialize the numbers in descending
       for(int i = 0; i < a.length; i++)
           a[i] = digit--;
      
       // Execute sorters
       executeSorters(a);
      
       /* Case 2: Numbers in ascending order - Smallest to Largest */
       // Initialize the numbers in ascending
       for(int i = 0; i < a.length; i++)
           a[i] = i+1;
      
       // Execute sorters
       executeSorters(a);      
   }

   public static void main(String[] args) {      
       // Test Case 1
       System.out.println("*********** Test Case 1 ***********");
       testCase1();
      
       // Test Case 2
       System.out.println("*********** Test Case 2 ***********");
       testCase2();
   }

}

Sample Output

First Set of Test

ARRAY SIZE: 2 ARRAY SIZE: 64 Algorithm: "Bubble Sort" NumItems"0" NumComparisons:"0" NumMoves"0" NumNanoseconds "377 Algorithm"Bubble Sort" NumItems: "1066" NumComparisons: "1066" NumMoves "3198" NumNanoseconds "77781" Algorithm"Selection Sort" NumItems"e" NumComparisons:"0" NumMoves"0" NumNanoseconds "755" Algorithm : "Selection Sort" NumItems"60" NumComparisons: "185" NumMoves: "180" NumNanoseconds "201250" Algorithm"Insertion Sort" NumItems"0" NumComparisons:"0" NumMoves"0" NumNanoseconds "756" Algorithm"Insertion Sort" NumItems "61" NumComparisons: "61" NumMoves "122" NumNanoseconds "9061" Algorithm "Merge Sort" NumItems"3' NumComparisons: "1" NumMoves: "4'" NumNanoseconds "7174" Algorithm "Merge Sort" NumItems"371" NumComparisons: "307" NumMoves: "768" NumNanoseconds "48708"

Second set of data

ARRAY SIZE: 4096 ARRAY SIZE: 4096 Algorithm: "Bubble Sort" NumItems"8386560" NumComparisons: "8386560" NumMoves "25159680" NumNanoseconds "14789067" Algorithm: "Bubble Sort" NumItems"e" NumComparisons:"0" NumMoves"0" NumNanoseconds "9951885" Algorithm"Selection Sort" NumItems: "2048" NumComparisons: "4194304" NumMoves "6144" NumNanoseconds "10000215" Algorithm"Selection Sort" NumItems"0" NumComparisons:"0" NumMoves"0" NumNanoseconds "6139834" Algorithm "Insertion Sort" NumItems "4095" NumComparisons: "4095" NumMoves 8190" NumNanoseconds "325097" Algorithm"Insertion Sort" NumItems"e" NumComparisons:"0" NumMoves"0" NumNanoseconds "100814" Algorithm "Merge Sort" NumItems:"28672" NumComparisons: "24576" NumMoves "98304" NumNanoseconds "499161" Algorithm "Merge Sort" NumItems:"28672" NumComparisons: "24576" NumMoves "98304" NumNanoseconds "1155773"