Sorting plus empirical algorithm evaluation.

You will experiment with the following three algorithms:

1. Bubble sort;

2. Quick sort; and

3. Merge sort.

Sorting

In this section you will need to implement Bubble sort, Quick sort and Merge Sort algorithms by extending a base abstract class. You will start with the following abstract class public abstract class ArraySort {

... abstract public void iSort(T[] inArray);

abstract public T[] oSort(T[] inArray);

public long iSortTimed(T[] inArray) { ... }

public void setComparator(Comparator comparator) { ... } }

You must 1) complete this class and 2) extend this abstract class (to implement the three sorting algorithms) by implementing its abstract methods.

Method iSort

Performs in-place sorting. The input array is replaced by a sorted version.

Method oSort

Performs out-of-place sorting. It preserves the input array, and returns a new sorted array.

Method iSortTimed

Performs in-place sorting and records the time it took to perform this sorting.

Method setComparator

Sets the comparator used by the sorting procedures.

Comparator Interface

It is important to emphasize that it is expected that your implementations will work with generic data type (), so you need to provide a mechanism of comparing two generic values. You will implement a Comparator interface for the generic types used in your program.

public interface Comparator {

public int compare(T a, T b); }

The only method that requires implementation is compare(). The return value of compare(a,b) is defined as: 1 if a

Implement the abstract class ArraySort

Extend the abstract class ArraySort to implement BubbleSort, MergeSort and Quicksort. Implement the comparator interface for the following types: Integer, String, and Float. o The comparator implementations must also accept a Boolean flag indicating whether to compare in ascending order or descending order, e.g. the constructor for IntegerComparator looks like public IntegerComparator(boolean ascend)