Objectives of this Lab

To actually write code for two sorting algorithms: bubble and selection sort, and

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

Make an Eclipse project named R21.

Download Sorting.java and FillArray.java.

Look through the provided code, which your TA will help explain.

First, complete the bubbleSort method in Sorting.java.

Second, complete the selectionSort method in Sorting.java.

HINT 1: These algorithms are documented on the Internet.

HINT 2: Start with 10 elements and uncomment debug code in FillArray.java.

The provided code will verify your sorting code and measure performance.

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