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
- Download the skeleton for this project.
- Unpack the code into a new Eclipse Java project.
- Add in the JUnit library to your project settings if necessary.
- Run the Sortimator.java file in the
sorting.gui package
and verify that the GUI is displayed.
- 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 T 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.
- For each element in the list
- If the current element is smaller
than the element to its left, swap them.
- If you just made a swap, repeat this check for the next
two elements to the left.
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.
- Scan through the whole list from left to right.
- When you find elements out of order, swap them into correct order.
- If any elements were found out of order during this scan, repeat.
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
- If the start and end are at least one element apart
- Split the elements in half and call mergeSortHelper on each sublist
- Merge together the two sublists found in between start and end
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.
- Make a new sublist that contains the first elements in the list, from start up to but not including
(start + end) / 2.
- Make a new sublist that contains the last elements in the list, from
(start + end) / 2 up to but not including end.
- Compare the first elements in these two lists
- Set the smaller one to be the first element in the original list.
- Repeat this comparison and setting, shifting right in the sublist that just contained the smaller
element, until you reach the end of one sublist.
- Add elements in order
from the sublist with remaining elements to the original list.
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
- If the start and end are at least one element apart
- Partition the elements based on a randomly chosen pivot element
- Recursively apply quickSortHelper to two sublists partition, where the two
sublists are split based
The partition method should have the same parameters as the
quickSortHelper method.
- Select the last element of the sublist as the
pivot element.
- Scan each other element in the list, and ensure that an element is swapped
into the front portion of the list if it is smaller than the pivot element.
- This can be accomplished by remembering how many elements so far
have been found to be smaller than the pivot, and placing the
next encountered smaller element at this count spot.
- Finally, move the partition to the spot in the list directly
after all of the elements smaller than it.
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
- To earn a D, finish Step 1
- To earn a C, finish the above and Steps 2 and 3.
- To earn a B, finish the above and Step 4.
- To earn a A, finish the above and Step 5.
- To earn a 100, finish the above and Step 6.
© Mark Goadrich, Hendrix College