Overview In this assignment you will be implementing and testing all three sort

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.

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

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

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.