# CSCI 151 Lab: The Sortimator

## Overview

In this lab, we will implement multiple sorting algorithms and compare their perfomance.## Step 1: Setup

- Download the skeleton for this project.
- Unpack the code into a new Eclipse Java project.
- Run the
`SorterTest.java`

file in the`sorting.algorithms`

package and verify that everything runs correctly.

`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 takes
an `ArrayList`

to be sorted.
First, as usual, we can access the elements in the list with
the `get`

method, determine its size with
the `size`

method, and set an element at a particular index
with the `set`

method.

Next, since we have an `ArrayList`

of generic elements, we
need to call the `compareTo`

method. As discussed in class,
this method returns an integer: equal to 0 if the two elements are the
same, negative if the first is smaller than the second, and positive
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*. Since we already implemented this algorithm together in class, the focus is on becoming familiar with the particular framework used for this lab, and practicing translating our detailed pseudocode into actual working Java code.

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 something like

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

### Step 2.1: Implementation

As discussed in class, insertion sort can be implemented as follows:for (numSorted = 1; numSorted < n; numSorted++) { toInsert = a[numSorted] i = numSorted - 1 while (i >= 0 && toInsert < a[i]) { a[i+1] = a[i] i-- } a[i+1] = toInsert; }Of course this is just pseudocode; you will need to translate it into working Java.

### Step 2.2: Testing

Run the`SorterTester`

to
make sure your implementation has the correct behavior. It will
automatically notice and test any new sorters you create.
## Step 3: BubbleSorter

Bubble sort is known for the simplicity of its 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

As discussed in class, bubble sort can be implemented with the following algorithm:- Repeatedly scan through the whole list from left to right.
- When you find adjacent elements out of order, swap them into the correct order.

### 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 recursive`mergeSortHelper`

method. During the recursion, we need to keep track of the start and
end indices of the current sublist. These indices should be additional
parameters to `mergeSortHelper`

along with the list. As we
did with binary search, the sublist should include
the `start`

index and extend up to *but not including*the

`end`

index. So, `sortAlgorithm`

will
initially call the `mergeSortHelper`

method with a starting
index of 0 and an end index equal to the `size()`

of the
list.
`mergeSortHelper`

has the following structure:

- If the current sublist is more than one element long:
- Split the elements in half and call
`mergeSortHelper`

on each sublist - Merge together the two sublists, storing the resulting merged elements back in the original array.

- Split the elements in half and call

To complete this implementation, we need a `merge`

method,
which takes the same parameters as `mergeSortHelper`

(a
list, start, and end indices), and merges the two half sublists into
one, assuming they are already sorted.

- Create a new list to hold the merged elements.
- Create indices
`i`

and`j`

to iterate through the two sublists, with`i`

beginning at`start`

, and`j`

beginning at`(start+end)/2`

. - Compare the elements at
`i`

and`j`

, adding the smaller one to the new list. - Repeat this comparison and setting until you reach the end of one sublist.
- Add any remaining elements from either sublist to the end of the new list.
- Finally, copy the merged elements from the new list back into the original array.

### Step 4.2: Testing

Run your code through the`SorterTester`

suite to make
sure your implementation has the correct behavior.
## Step 5: QuickSorter

Whereas merge sort has an easy journey down the recursion and the real work happens on the way back up while merging,*quicksort*reverses this scheme. Before recursing, quicksort partitions the elements of the list, into two (ideally equal-sized) portions, placing the elements smaller than a 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.

Create a `QuickSorter`

class to implement quicksort.

### Step 5.1: Implementation

Again, we will need a recursive helper function, augmenting with the start (inclusive) and end (exclusive) indices of the sublist.`quickSortHelper`

has the following structure:
- If the current sublist has more than one element:
`partition`

the elements into two sublists, returning the resulting position of the pivot element.- Recursively apply
`quickSortHelper`

to the two sublists.

The `partition`

method should have the same parameters as the
`quickSortHelper`

method, and works as follows:

- Select the last element of the sublist as the
`pivot`

element. - Scan all the other elements 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, swap the partition to the spot in the list directly after all of the elements smaller than it.

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.
## What to Hand In

Submit your```
InsertionSorter.java
```

, ```
BubbleSorter.java
```

, ```
MergeSorter.java
```

and
```
QuickSorter.java
```

implementations.
## 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, use good code style and documentation throughout.

© Mark Goadrich, Hendrix College