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; } } }

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

/** * * This interface will be used by various classes to sort an array Integer objects. * You will write three classes that implement this interface: * *

*
1. BubbleSort
*
2. InsertionSort
*
3. SelectionSort
*

* * @author Sameh A. Fakhouri * */

public interface SortInterface {

/** * * This method is called to sort the given array of Integer objects. At the * completion of this method, the array will be sorted. * * @param arrayToSort This is the array that contains all the Integer objects * that need to be sorted. */ public void sort(Integer[] arrayToSort); }

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.

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.

Driver Interface

/** * * @author Sameh A. Fakhouri * */ public interface DriverInterface {

/** * This enum is used to specify the type of Array. All arrays used in this * assignment will be arrays of Integer: * *

*
1. Equal - The elements in the array are all equal.
*
2. Random - The elements in the array are randomly generated.
*
3. Increasing - The elements of the array are arranged in increasing order.
*
4. Decreasing - The elements of the array are arranged in decreasing order.
*
5. IncreasingAndRandom - The first 90% of the elements are arranged in increasing order and the last 10% * of the elements are randomly generated.
*

* */ public static enum ArrayType {Equal, Random, Increasing, Decreasing, IncreasingAndRandom}; /** * This enum is used to specify the desired sort algorithm: * *

*
1. BubbleSort - Indicates the Bubble Sort algorithm.
*
2. SelectionSort - Indicates the Selection Sort algorithm.
*
3. InsertionSort - Indicates the Insertion Sort algorithm.
*

* */ public static enum SortType {BubbleSort, SelectionSort, InsertionSort}; /** * * This method is used to create a new array of Integer objects of the type and size * specified. * * @param arrayType This parameter specifies the type of array to create. See the enum {@link ArrayType}. * * @param arraySize This parameter specifies the size of array to create. * * @return The method will return the array of Integer objects that was created. * */ public Integer[] createArray(ArrayType arrayType, int arraySize); /** * * This method will run the specified sort type a specified number of times. Each time the sort run * the method will obtain a new array to sort. The array will be of the specified type and size. * * @param sortType This parameter specifies the sort algorithm that will be used. See {@link SortType}. * * @param arrayType This parameter specifies the type of array to create each time the sort is run. * See the enum {@link ArrayType}. * * @param arraySize This parameter specifies the size of array to create each time the sort is run. * * @param numberOfTimes This parameter specifies the number of times to run the specified sort. * * @return The method must return the RunTime class that was used to save the measured run times for the * sort performed. * */ public RunTime runSort(SortType sortType, ArrayType arrayType, int arraySize, int numberOfTimes);

}

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