Feel free to work in pairs.
We have studied two sorting algorithms in class: selection sort and insertion sort. In this part of the lab, you will study one more: bubble sort first. Then, we will compare those three.
Search on the Internet for bubble sort and find an algorithm
description for
it. This one
is okay, but you are welcome to find another if you can find a
better one. Then, implement a class named Bubble in a file
named Bubble.java. Introduce a function
named bubbleSort that implements bubble sort. The signature
of bubbleSort should be quite similar to that of
either selectionSort or insertionSort. Introduce a main
method in the class as well, as we did with selection sort and
insertion sort. Fully implement and make Bubble run
without any error.
Create a class named Compare in a file
named Compare.java. Include each of the three sorting
functions in this class.
Now, modify each of the three sorting functions so that each can
count the number of comparisons (between elements) being made as the
array of numbers is sorted. Each sorting function will return
an int which is the count. For selection sort, you may
use the simpler version that we studied in class or the other
that was included but commented out.
Include a main function in Compare that sets up
an array which contains 100 random numbers in it. With
that same array call each of the three sorting functions and
output the number of comparisons made in each case to the standard
output device, i.e., the screen.
This time again create an array of 100 integers, but put them in ascending order, e.g., 1, 2, . . ., 100, and obtain the number of comparisons made in each sorting function and output them to the screen. You can write a function that creates an array containing these numbers, right? Not by manually typing all 100 numbers but using a loop!
This time yet again create an array of 100 integers, but put them in descending order, e.g., 100, 99, . . ., 1, and obtain the number of comparisons made in each sorting function and output them to the screen.
Once more: this time put the same number 100 times in the array, e.g., 23, 23, . . ., 23 (100 of them), and obtain the number of comparisons made in each sorting function and output them to the screen.
Hopefully, you will see some differences in each of the cases among
three sorting algorithms. Summarize what you observed and add it
as comments at the top of Compare.java.
When you are done with these programs, feel free to leave the lab.