Develop JUnit tests for five standard sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Merge Sort.

Implement the above sorts. Test your code.

Measure your codes performance over increasingly large datasets.

Your sorting project will contain the following classes:

SortInterface interface (below)

import java.util.ArrayList;

public interface SortInterface {

public void bubblesort(ArrayList list, int lowindex, int

highindex, boolean reversed);

public void insertionsort(ArrayList list, int lowindex, int

highindex, boolean reversed);

public void selectionsort(ArrayList list, int lowindex, int

highindex, boolean reversed);

public void shellsort(ArrayList list, int lowindex, int

highindex, boolean reversed);

public void mergesort(ArrayList list, int lowindex, int

highindex, boolean reversed);

}

Sort class, which implements the interface class

SortTest class, JUnit test cases for your Sort methods.

Profiler class, which contains your measurement code

It is critically important that:

Your sorting class be named Sort

Your Sort class has a constructor that takes no parameters

Your Sort class implements the SortInterface interface as is, without changes.

Otherwise, you will fail the WebTA tests and you will lose points! Also, check to make sure your sorting algorithms are correct. Several of these algorithms are complicated and it is easy to make a subtle mistake when coding. Be sure to read the detailed requirements for each sorting algorithm listed below. You should not use any instance variables for this assignment, only local method variables. You are encouraged to write as many private helper methods as you need.

1. Sorting Algorithms in Detail

Create a Sort class that implements the SortInterface interface. Implement the following methods in the Sort class.

public void bubblesort( ArrayList list, int lowindex, int highindex, boolean reversed )

This is the most straightforward of the sorting algorithms to code. But the devil is in the details. Your Bubble Sort needs to work over a range of indices in the list and you need to be able to sort the list backwards. Your algorithm should sort all elements in the array in the range lowindex..highindex (inclusive). You should not touch any of the data elements outside the range lowindex .. high index. The return type is void because you directly modify the given list. This is known as a destructive sort because the original elements are irrevocably changed.

public void insertionsort( ArrayList list, int lowindex, int highindex, boolean reversed )

Insertion Sort is also very intuitive to code. You've used this method before for organizing a hand of cards. Again, your insertion sort needs to work over a range of indices in the list and you need to be able to sort the list backwards, if the reversed flag is true. Your algorithm should sort all elements in the array in the range lowindex..highindex (inclusive). And you should not touch any of the data elements outside the range lowindex .. high index. This is also a destructive sort; also called an in-place sort.

public void selectionsort( ArrayList list, int lowindex, int highindex, boolean reversed )

Also very straightforward. As with insertion sort above, your sorting algorithm needs to work over a range of indicies in the list, and you need to be able to sort the list backwards, if the reversed flag is true. Your algorithm should sort all elements in the array in the range lowindex..highindex (inclusive). You should not touch any of the data elements outside the range lowindex .. highindex. This will also be an in-place sort.

public void shellsort( ArrayList list, int lowindex, int highindex, boolean reversed )

Your implementation of Shell Sort needs to use Hubbard's increments: 1, 3, 7, 15, ... Math.pow(2,k)-1. Thus if the range of elements contains 100 elements, the first sort would be a 63-sort, followed by a 31-sort, 15-sort, 7-sort, 3-sort and 1-sort. (NOTE: The code in the video uses Math.pow(3,k)+1). As with insertion sort, you need to be able to sort only a range of the list, and also be able to reverse-sort the list.

public void mergesort( ArrayList list, int lowindex, int highindex, boolean reversed )

Much as above, this function sorts a list using merge sort. You need to be able to sort only a range of the list, and also be able to reverse-sort the list.