CSCI 151 - Lab 8
The Sortimator


Overview

In this lab, we will implement multiple sorting algorithms and compare their perfomance.

Materials

Description

Step 1 - Setup

  1. Download the skeleton for this project.
  2. Unpack the code into a new Eclipse Java project.
  3. Add in the JUnit library to your project settings if necessary.
  4. Run the Sortimator.java file in the sorting.gui package and verify that the GUI is displayed.
  5. Click the Scramble and then Sort buttons to watch an animation of the GnomeSort algorithm.
Take a look at the code inside GnomeSorter.java. This is an example algorithm demonstrating elements that you should use in your implementations below. Each algorithm will need to implement the sortAlgorithm method, which brings in an ArrayList to be sorted.

First, we can access the elements in the list with the get method, and determine its size with the size method. However, notice that we do not use the set element of the list. Instead, we call our own set method, which takes the list to be set, the index that will be set, and the element to set in the index location. This roundabout method is used to assist with the animation. You will need to use this method in all of your implementations.

Next, since we have an ArrayList of generic elements, we need to call the compareTo method. This will return an integer, equal to 0 if the two elements are the same, -1 if first is smaller than the second, and 1 if the first is larger than the second, according to whatever ordering scheme is defined. We will want our resulting array to be sorted from smallest to largest.

Also note that there is a swap going on in this algorithm. You might consider implementing a swap method as you code below to make your life easier.

Step 2 - InsertionSorter

Your first sorting algorithm to implement is Insertion Sort. You will incrementally placing elements into a sorted array.

Create a new class called InsertionSorter. To fit into the Sortimator hierarchy, it will need to extend the generic Sorter class. Also, the generic type E will need to extend the Comparable interface. The name of your class should be

InsertionSorter<E extends Comparable<E>> extends Sorter<E>

Step 2.1 - Implementation

InsertionSort can be implemented with the following algorithm.

Step 2.2 - Testing

Run your code through the SorterTester suite to make sure your implementation has the correct behavior.

Step 3 - BubbleSorter

Bubble sort is known for its simplicity of code. Repeated passes through the data quickly push the largest elements to the end, and slowly drag the smallest elements to the front of the list.

The name of your class should be

BubbleSorter<E extends Comparable<E>> extends Sorter<E>

Step 3.1 - Implementation

BubbleSort can be implemented with the following algorithm. To save time, each scan can reduce the elements it examines by one, since on the first pass, we can guarantee that the highest element will be in the right location, and on the second pass, the second-highest element will be in the right location, etc.

Step 3.2 - Testing

Run your code through the SorterTester suite to make sure your implementation has the correct behavior.

Step 4 - MergeSorter

Merge sort uses recursion to repeatedly split the given list into smaller lists, sort the smaller lists, and then combine the sorted sublists into one sorted list.

The name of your class should be

MergeSorter<E extends Comparable<E>> extends Sorter<E>

Step 4.1 - Implementation

First, you will need to create a mergeSortHelper method. In order to do recursion, we will need to track the start and end indicies of our sublists. The start and end should be additional parameters along with the list. Use end as we have in other contexts, to be the stoping index, going up to but not including this index. So, our sortAlgorithm will call the mergeSortHelper method with start as 0 and end as the size of the list.

mergeSortHelper has the following structure

To complete this method, we need a merge method, which brings in the same parameters as above. We will need to make copies of our elements into two lists, and then add them back in so that the elements are now in sorted order.

Step 4.2 - Testing

Run your code through the SorterTester suite to make sure your implementation has the correct behavior.

Step 5 - QuickSorter

Whereas MergeSort was an easy journey down the recursion but complicated merging back up, QuickSort reverse this scheme. Before recursing, QuickSort partitions the elements of the list, hopefully into two equal-sized portions, placing the elements smaller than a randomly chosen pivot element to the left and those elements larger to the right. These sublists will be semi-sorted, and then repeatedly partitioned until all elements are in the correct order.

The name of your class should be

QuickSorter<E extends Comparable<E>> extends Sorter<E>

Step 5.1 - Implementation

Again, we will need a recursive helper function, augmenting with the start and end of the sublist. quickSortHelper has the following structure

The partition method should have the same parameters as the quickSortHelper method.

To speed up your algorithm, avoid making swaps when the two locations being swapped are the exact same index.

The partition method will need to return the location of the pivot element after all swaps have been made, as this is the dividing line between the two sublists.

Step 5.2 - Testing

Run your code through the SorterTester suite to make sure your implementation has the correct behavior.

Step 6 - Evaluation

Describe in your own words the strengths and weaknesses of each of the four implementations above. Use the Sortimator class to run each algorithm 3 times, on a list of size 20. Record the number of Array Updates that each method executes, as found through the GUI.

What to Hand In

Submit your InsertionSorter.java, BubbleSorter.java, MergeSorter and QuickSorter.java implementations, along with a document for your evaluation in Step 5.

Grading


© Mark Goadrich, Hendrix College