Lab 21 - Basic Sorting Lab

---

Objectives of this Lab

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

---

Description

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

// Bubble sorting public static void bubbleSort(double[] values) { // Put the code for bubble sort here } // Selection sorting public 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.
3. Look through the provided code, which your TA will help explain.
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 the Internet.
7. HINT 2: Start with 10 elements and uncomment debug code in FillArray.java.
8. The provided code will verify your sorting code and measure performance.
9. When your sorting code is verified, measure performance with 50000 elements.

Testing

Here is the approximate output of the program after all methods and test code are complete, for sorting 50000 elements. Don't worry about your output exactly matching, since your performance may vary somewhat:

COMPLETELY RANDOM: Bubble sort of 50000 elements = 3389 milliseconds Selection sort of 50000 elements = 684 milliseconds Insertion sort of 50000 elements = 1203 milliseconds Quick sort of 50000 elements = 16 milliseconds HALF SORTED: Bubble sort of 50000 elements = 1676 milliseconds Selection sort of 50000 elements = 676 milliseconds Insertion sort of 50000 elements = 597 milliseconds Quick sort of 50000 elements = 2 milliseconds REVERSE ORDER: Bubble sort of 50000 elements = 855 milliseconds Selection sort of 50000 elements = 920 milliseconds Insertion sort of 50000 elements = 578 milliseconds Quick sort of 50000 elements = 1 milliseconds ALREADY SORTED: Bubble sort of 50000 elements = 932 milliseconds Selection sort of 50000 elements = 675 milliseconds Insertion sort of 50000 elements = 0 milliseconds Quick sort of 50000 elements = 1 milliseconds 

---

---

here

https://www.toptal.com/developers/sorting-algorithms

sorting.java

// Sorting.java - initial code for sorting lab

// Author: ????? // Date: ????? // Class: CS163/CS164 // Email: ????? 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

// FillArray.java - utility code to fill array with random values

// Author: Chris Wilcox, original by Russ Wakefield // Date: 11/20/2016 // Class: CS163/CS164 // Email: wilcox@cs.colostate.edu 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; } }