Overview

In this assignment you will be implementing and testing all three sort algorithms: Bubble Sort , Selection Sort , and Insertion Sort .

In additions, you will also be writing a driver to test the search algorithms and you will be measuring the run times of each search.

You will also be using the RunTime class that you created for Homework 1.

Finally, you will be analysing and comparing the performance of the three sort algorithms based on the type of array that was being sorted and the run times you computed.

Details

RunTime Class

import java.util.Arrays;

public class RunTime implements RuntimeInterface {

private static final int MAX = 10; private long[] runtimes; private int count; public RunTime() { this.runtimes = new long[MAX]; this.count += 0; }

@Override public void addRuntime(long runTime) { if (this.count == MAX) { for (int i = 0; i < (MAX - 1); i++) { this.runtimes[i] = this.runtimes[i + 1]; } this.runtimes[MAX - 1] = runTime; } else {

this.runtimes[count] = runTime; this.count += 1; } }

@Override public double getAverageRunTime() { double sum = 0; for (int i = 0; i < this.count; i++) { sum += this.runtimes[i]; } return (sum / this.count); }

@Override public long getLastRunTime() { return this.runtimes[this.count - 1]; }

@Override public long[] getRunTimes() { return Arrays.copyOf(this.runtimes, this.count); }

@Override public void resetRunTimes() { for (int i = 0; i < MAX; i++) { this.runtimes[i] = 0; } } }

Runtime Interface

public interface RuntimeInterface { public void addRuntime(long runTime); public double getAverageRunTime(); public long getLastRunTime(); public long[] getRunTimes(); public void resetRunTimes(); }

BubbleSort Class

You will write the BubbleSort.java class which will inherit from RunTime.java and implement the Sort Interface using the Bubble Sort algorithm. The interface may be downloaded fromSortInterface.java

Please note that your sort method must measure the run time and add it to the RunTime class by using the addRunTime() method.

SelectionSort Class

You will write the SelectionSort.java class which will inherit from RunTime.java and implement the Sort Interface using the Selection Sort algorithm. The interface may be downloaded from SortInterface.java

Please note that your sort method must measure the run time and add it to the RunTime class by using the addRunTime() method.

InsertionSort Class

You will write the InsertionSort.java class which will inherit from RunTime.java and implement the Sort Interface using the Insertion Sort algorithm. The interface may be downloaded from SortInterface.java

Please note that your sort method must measure the run time and add it to the RunTime class by using the addRunTime() method.

Sort Interface

public interface SortInterface { public void sort(Integer[] arrayToSort); }

Driver Class

You will write the Driver.java class which will implement the Driver Interface . The interface may be downloaded from DriverInterface.java

Output From Driver Main Method

Please note that, in addition to implementing the DriverInterface, you are also required to write your own public static main(String[] args) method in Driver.java.

Your main() method will have to call the runSort() method to sort each of the following array types ten times for each sort algorithm:

1,000 equal Integers.

1,000 random Integers.

1,000 increasing Integers.

1,000 decreasing Integers.

1,000 increasing and random Integers.

10,000 equal Integers.

10,000 random Integers.

10,000 increasing Integers.

10,000 decreasing Integers.

10,000 increasing and random Integers.

For each call to the runSort() method to sort an ArrayType using a SortType ten times, your main() method will produce the following output:

SortType, ArrayType, Array Size -------------------------------------------------------------------------------------------------------------- runTime1 runTime2 runTime3 runTime4 runTime5 runTime6 runTime7 runTime8 runTime9 runTime10 --- Average runTime 

Driver Interface

public interface DriverInterface { public static enum ArrayType {Equal, Random, Increasing, Decreasing, IncreasingAndRandom}; public static enum SortType {BubbleSort, SelectionSort, InsertionSort}; public Integer[] createArray(ArrayType arrayType, int arraySize); public RunTime runSort(SortType sortType, ArrayType arrayType, int arraySize, int numberOfTimes); }

Each Class needs to be seperate and I am not sure how to do it.