[Solved] Objectives Lab Actually Write Code Two Sorting Algorithms Bubble Selection Sort See Differ Q37265462

Objectives of this Lab

1. To actually write code for two sorting algorithms: bubble andselection sort, and
2. to see the difference in performance between these andquicksort provided by Java.

Description

This lab requires you to complete the Sorting.java class, whichimplements four different sorting algorithms: bubble, selection,insertion, and quicksort. The TA will help you visualize thesorting algorithms, using the excellent website here. For this lab,the insertion sorting code is provided as an example, and quicksortis provided by Java in the form of the Arrays.sort() method.Arrays.sort() uses quicksort for primitives and mergesort forobjects. A second class named FillArray.java provides a couple ofuseful methods for filling an array with random numbers andchecking whether an array is sorted. Here are the two methods youmust implement:

// Bubble sortingpublic static void bubbleSort(double[] values) { // Put the code for bubble sort here}// Selection sortingpublic static void selectionSort(double[] values) { // Put the code for selection sort here}

Instructions

1. Make an Eclipse project named R21.
2. Download Sorting.java and FillArray.java. (these are atthe bottom of the page)
3. Look through the provided code, which your TA will helpexplain.
4. First, complete the bubbleSort method in Sorting.java.
5. Second, complete the selectionSort method in Sorting.java.
6. HINT 1: These algorithms are documented on theInternet.
7. HINT 2: Start with 10 elements and uncommentdebug code in FillArray.java.
8. The provided code will verify your sorting code and measureperformance.
9. When your sorting code is verified, measure performance with50000 elements.

Testing

Here is the approximate output of the program after all methodsand test code are complete, for sorting 50000 elements. Don’t worryabout your output exactly matching, since your performance may varysomewhat:

COMPLETELY RANDOM:Bubble sort of 50000 elements = 3389 millisecondsSelection sort of 50000 elements = 684 millisecondsInsertion sort of 50000 elements = 1203 millisecondsQuick sort of 50000 elements = 16 millisecondsHALF SORTED:Bubble sort of 50000 elements = 1676 millisecondsSelection sort of 50000 elements = 676 millisecondsInsertion sort of 50000 elements = 597 millisecondsQuick sort of 50000 elements = 2 millisecondsREVERSE ORDER:Bubble sort of 50000 elements = 855 millisecondsSelection sort of 50000 elements = 920 millisecondsInsertion sort of 50000 elements = 578 millisecondsQuick sort of 50000 elements = 1 millisecondsALREADY SORTED:Bubble sort of 50000 elements = 932 millisecondsSelection sort of 50000 elements = 675 millisecondsInsertion sort of 50000 elements = 0 millisecondsQuick sort of 50000 elements = 1 milliseconds

Here are the two linked files

Sorting.java

import java.util.Arrays;public class Sorting { // Size of array private static final int MAXSIZE = 50000; // Main entry point public static void main(String args[]) { // Initialize data in different ways for (int option = 0; option < 4; option++) { switch (option) { case 0: System.out.println(“COMPLETELY RANDOM:”); break; case 1: System.out.println(“HALF SORTED:”); break; case 2: System.out.println(“REVERSE ORDER:”); break; case 3: System.out.println(“ALREADY SORTED:”); } // Verify and measure different kinds of sorting for (int sort = 0; sort < 4; sort++) { measureSorting(option, sort); } System.out.println(); } } private static void measureSorting(int option, int sort) { long starttime = 0; // starting clock tick long finaltime = 0; // ending clock tick FillArray array = new FillArray(MAXSIZE); String label = “”; double[] unsortedArray = array.fillArray(option); starttime = System.nanoTime(); switch (sort) { case 0: bubbleSort(unsortedArray); // student code label = “Bubble”; break; case 1: selectionSort(unsortedArray); // student code label = “Selection”; break; case 2: insertionSort(unsortedArray); // provided code label = “Insertion”; break; case 3: Arrays.sort(unsortedArray); // native quicksort label = “Quick”; break; } finaltime = System.nanoTime(); // Make sure it is sorted array.checkArray(unsortedArray); // Print timing information long millis = (finaltime – starttime) / 1000000; // nano to micro System.out.println(label + ” sort of ” + MAXSIZE + ” elements = ” + millis + ” milliseconds”); } // Bubble sorting public static void bubbleSort(double[] values) { // STUDENT CODE HERE } // Selection sorting public static void selectionSort(double[] values) { // STUDENT CODE HERE } // Insertion sorting public static void insertionSort(double[] values) { int i,j; // Outer loop for (i = 1; i < values.length; i++) { // Current value double value = values[i]; // Inner loop for (j = i-1; j >= 0 && value < values[j]; j–) { values[j+1] = values[j]; } // Value is sorted values[j+1] = value; } }}

FillArray.java

import java.util.Random;public class FillArray { // Class variables private static double[] randomArray; private static int randomSize = 0; private static Random randomObject; // Constructor public FillArray(int size) { randomSize = size; randomArray = new double[size]; randomObject = new Random(); randomObject.setSeed(12345678); // guarantee repeatability for (int i = 0; i < size; i++) { randomArray[i] = randomObject.nextDouble() * size; } } // Fill an array with variants of random numbers public double[] fillArray(int option) throws IllegalArgumentException { double[] values = new double[randomSize]; switch (option) { case 0: // Completely random for (int i = 0; i < randomSize; i++) values[i] = randomArray[i]; break; case 1: // Half sorted int half = randomSize / 2; for (int i = 0; i < half; i++) values[i] = randomArray[i]; for (int i = half + 1; i < randomSize; i++) values[i] = (double)i; break; case 2: // Reverse order for (int i = 0; i < randomSize; i++) values[randomSize – i – 1] = (double)i; break; case 3: // Already sorted for (int i = 0; i< randomSize; i++) values[i] = (double)i; break; default: throw new IllegalArgumentException(); } return values; } // Check an array to make sure it is sorted public boolean checkArray(double[] array) { // Useful for debugging // System.out.println(Arrays.toString(array)); // Check array reference if (array == null) { System.out.println(“Null array passed to checkArray!”); return false; } // Check array size else if (array.length != randomSize) { System.out.println(“Incorrect size array passed to checkArray!”); return false; } // Check array contents else { // System.out.println(“ARRAY: ” + Arrays.toString(array)); for (int i = 0; i < array.length – 1; i++) if (array[i] > array[i + 1]) { System.out.println(“Array not sorted correctly, ” + array[i] + ” at ” + i + ” is greater than ” + array[i + 1] + ” at ” + (i + 1)); return false; } } return true; }}

Expert Answer

---

Answer to Objectives of this Lab To actually write code for two sorting algorithms: bubble and selection sort, and to see the diff… . . .