# CSCI 151 Lab: The Sortimator

## Overview

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

## Step 1: Setup

2. Unpack the code into a new Eclipse Java project.
3. Run the SorterTest.java file in the sorting.algorithms package and verify that everything runs correctly.
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 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.
To save time, each scan can reduce the elements it examines by one, since after the first pass, we can guarantee that the largest element will be in the rightmost location; on the second pass, the second-highest element will be in the second-rightmost location, *etc.* As a further optimization, bubble sort can stop after a pass which performs no swaps.

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

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

## What to Hand In

Submit your  InsertionSorter.java  ,  BubbleSorter.java  ,  MergeSorter.java  and  QuickSorter.java  implementations.