Overview In this assignment you will be implementing and testing all three sort
ID: 3890039 • Letter: O
Question
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 sort.
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
You will copy the RunTime class that you created in Homework 1 to the project you are using for this assignment.
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.
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.
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:
Analysis:
Using the run time tables you created by running Driver.main(), copy your results into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:
Which sort worked best on data in constant or increasing order (ie already sorted data)? Why do you think this sort worked best?
Did the same sort do well on the case of mostly sorted data? Why or why not?
In general, did the ordering of the incoming data affect the performance of the sorting algorithms? Please answer this question by referencing specific data from your table to support your answer.
Which sort did best on the shorter (ie n=1,000) data sets? Did the same one do better on the longer (ie n=10,000) data sets? Why or why not? Please use specific data from your table to support your answer.
In general, which sort did better? Give a hypothesis as to why the difference in performance exists.
Are there results in your table that seem to be inconsistent? (ex. If I get run times for a sort that look like this {1.3, 1.5, 1.6, 7.0, 1.2, 1.6, 1.4, 1.8, 2.0, 1.5] the 7.0 entry is not consistent with the rest). Why do you think this happened?
Please submit the completed assignment on the Mimir Platform Website .
You must submit your .java files as a zip file of only the classes and interfaces specified above.
Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted.
SortInterface.java:
/**
*
* This interface will be used by various classes to sort an array Integer objects.
* You will write three classes that implement this interface:
*
*
*
*
*
*
BubbleSort
InsertionSort
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);
}
DriverInterface.java:
/**
*
* @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:
*
*
*
*
*
*
*
*
Equal - The elements in the array are all equal.
Random - The elements in the array are randomly generated.
Increasing - The elements of the array are arranged in increasing order.
Decreasing - The elements of the array are arranged in decreasing order.
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:
*
*
*
*
*
*
BubbleSort - Indicates the Bubble Sort algorithm.
SelectionSort - Indicates the Selection Sort algorithm.
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);
}
import java.util.Arrays;
public class RunTime implements RuntimeInterface {
private static final int MAX = 10;
// Instance variables
private long[] runtimes;
private int count;
/**
* Constructor
*/
public RunTime() {
this.runtimes = new long[MAX];
this.count += 0;
}
/**
* Adds a runtime
*/
@Override
public void addRuntime(long runTime) {
if (this.count == MAX) {
// If total runtimes is MAX, shift all runtimes 1 position up
for (int i = 0; i < (MAX - 1); i++) {
this.runtimes[i] = this.runtimes[i + 1];
}
// Add the new runtime at MAX - 1
this.runtimes[MAX - 1] = runTime;
} else {
// Add the new runtime
this.runtimes[count] = runTime;
// Increment count
this.count += 1;
}
}
/**
* Obtain the average runtime
*/
@Override
public double getAverageRunTime() {
double sum = 0;
for (int i = 0; i < this.count; i++) {
sum += this.runtimes[i];
}
return (sum / this.count);
}
/**
* Retrieve the last runtime
*/
@Override
public long getLastRunTime() {
return this.runtimes[this.count - 1];
}
/**
* Returns an array of long values representing the last 10 runtimes
*/
@Override
public long[] getRunTimes() {
return Arrays.copyOf(this.runtimes, this.count);
}
/**
* Reset all 10 linear search times to zero
*/
@Override
public void resetRunTimes() {
for (int i = 0; i < MAX; i++) {
this.runtimes[i] = 0;
}
}
}
Explanation / Answer
Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects is small enough to fits into the main memory, sorting is called internal sorting. If the number of objects is so large that some of them reside on external storage during the sort, it is called external sorting. In this chapter we consider the following internal sorting algorithms
Bucket sort
Bubble sort
Insertion sort
Selection sort
Heapsort
Mergesort
O(n) algorithms
Bucket Sort
Suppose we need to sort an array of positive integers {3,11,2,9,1,5}. A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.
Suppose we are sorting a large number of local phone numbers, for example, all residential phone numbers in the 412 area code region (about 1 million) We sort the numbers without use of comparisons in the following way. Create an a bit array of size 107. It takes about 1Mb. Set all bits to 0. For each phone number turn-on the bit indexed by that phone number. Finally, walk through the array and for each bit 1 record its index, which is a phone number.
We immediately see two drawbacks to this sorting algorithm. Firstly, we must know how to handle duplicates. Secondly, we must know the maximum value in the unsorted array.. Thirdly, we must have enough memory - it may be impossible to declare an array large enough on some systems.
The first problem is solved by using linked lists, attached to each array index. All duplicates for that bucket will be stored in the list. Another possible solution is to have a counter. As an example let us sort 3, 2, 4, 2, 3, 5. We start with an array of 5 counters set to zero.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.