|
Other-worldly Bubble Sort |
10 points
Sorting -- putting things in order -- is an important task in programming. The easy-to-understand (and program) ways of sorting are called "quadratic" sorts and are relatively inefficient. The harder-to-understand (and program) ways of sorting are more efficient. The text describes a quadratic sort called 'selection sort' in Ch. 18. In this program, you will be programming another quadratic sort called a 'bubble sort'.
Visualizing Selection Sort
Let's first describe a selection sort. Selection sort works like this: to put an array into 'ascending order' (small to large): first find the smallest element in the entire array and swap it with the first element in the array. Then find the second-smallest element and swap it with the second element in the array. Then find the third-smallest element and swap it with the third element in the array. Continue this process through the entire array. When you are done, the smallest element will be in the first position, the second-smallest element will be in the second position, and so on. The array will be sorted.
Now let's visualize a selection sort. Visit youtu.be/92BfuxHn2XE. Pretty darn exciting, huh?
Bubble Sort
A bubble sort is another quadratic sort, and it is the sort we're going to program. A bubble sort works like this: compare the first two elements in the array. If they are in the right order, do nothing. If they are in the wrong order, swap them. Then move on to the second and third elements in the array. Same thing: if they are in the right order, do nothing. If they are in the wrong order, swap them. Continue comparing adjacent elements as you step through the entire array. Following this first pass through the array, the largest element will correctly be placed in the last position in the array.
Then start over at the first element and step through the entire array again. The only difference this time is that you do not need to access the last element in the array. It is correctly positioned after the first pass through the array.
Similarly, for the third pass through the array, both the last element and the next-to-last element in the array are correctly positioned. So you don't need to include them in your sort. So as the bubble sort progresses, it needs to operate on fewer and fewer elements in the array.
Now let's visualize a bubble sort. Visit youtu.be/JP5KkzdUEYI. This illustrates a bubble sort in action. Makes you want to write one of your own, doesn't it?
Zygon 11
The idea here is that the small planet Zygon 11, which orbits the star Betelgeuse, has contracted you to write a computer program to do some sorting. (And the Zygonites always pay well.) They have supplied a data file that includes the 10,000 most popular names on Zygon 11, which can be downloaded below. So your task is to put these 10,000 names in order.
You can download below the three Java source files that you work on.
BubbleSort.java
import
You want to import these classes: java.util.ArrayList; javax.swing.JOptionPane; java.io.FileWriter; and java.io.IOException.
private instance variables
In the 'private instance variable' section, declare an ArrayList 'list' and an integer 'number'.
constructor
The constructor 'BubbleSort' accepts the ArrayList 'a_list' as an argument. Set the instance variable 'list' equal to 'a_list'.
swap
This method exchanges 2 elements in 'list'. Note that it accepts 2 integers as arguments. These are the positions in 'list' whose elements are to be swapped. Declare Strings 'temp1' and 'temp2'. Use the .get() method of ArrayList to assign the String in position 'first' in 'list' to 'temp1'. Remember to cast this element in 'list' to a String. Do the same thing to assign the String in position 'second' in 'list' to 'temp2'. Finally, use the .set() method of ArrayList to swap the Strings. For example, the syntax to assign 'temp2' to position 'first' in 'list' is:
list.set(first, temp2);
Use similar syntax to assign 'temp1' to position 'second'.
getNumber
This method figures out how many elements the program should sort. This method is complete.
printSorted
Inside the 'try' section, declare 'writer' to be of type 'FileWriter', and create the 'writer' object with a call to 'new FileWriter()'. In the parentheses should go the name of the output file. Set up a FOR loop that runs from 0 to 'number':
for (i = 0; i < number; i++)
Inside the loop, use the .get() method of ArrayList and 'writer.write()' to print each element of 'list' to the output file. Close the FOR loop, and then close 'writer':
writer.close();
bubbleSort
The String class has a 'compareTo()' method for comparing 2 Strings. If the result of the call to 'compareTo()' is positive, then the first String comes later alphabetically than the second String. For example, "Wednesday".compareTo("Tuesday") is positive, because "Wednesday" comes after "Tuesday" alphabetically. When a call to 'compareTo()' is positive, you want to call your 'swap()' method to re-arrange the 2 Strings. When a call to 'compareTo()' is negative or zero, you shouldn't do anything, because those 2 Strings are correctly positioned.
Set up a loop that runs 'number' times. This means that you will pass through the entire ArrayList 'number' times.
Inside this loop, set up a second loop. The purpose of this inner loop is to pass through the ArrayList once, from element 0 to element 'number-1'. If 'i' is the loop index, pull elements 'i' and 'i+1' from 'list' using the .get() method. Then use 'compareTo()' to see if they need to be swapped. If the result of the call to 'compareTo()' is positive, make a call to the 'swap()' method to swap them.
BubbleSortTimer.java
readNames
After the variable 'in' is created, declare a boolean 'done' and set it to 'false'. Also declare a String 'name'. Set up a WHILE loop that runs as long as 'done' is 'false'. Inside the loop, call 'in.readLine()' and assign the result to 'name'. In an IF statement, check if 'name' is 'null'. If it is, you've reached the end of the input file, and you should set 'done' equal to 'true'. If 'name' is not equal to 'null', call the .add() property of the ArrayList to add 'name' to 'list':
list.add(name);
Close the WHILE loop, and then close 'reader'.
runSort
This method runs the show. First call the method 'readNames'. Then create a StopWatch object with this syntax:
StopWatch timer = new StopWatch();
Create a BubbleSort object like this:
BubbleSort sorter = new BubbleSort(list);
Call the 'getNumber' method of the 'sorter' object and assign the result to an integer 'number'. The call to 'getNumber' produces an inputDialog that looks like this:
Call the 'start' method of the 'timer' object (This starts the stop watch). Call the 'bubbleSort' method of 'sorter' (This does the actual sorting of the names into alphabetical order). Call the 'stop' method of 'timer'. Call the 'printSorted' method of
'sorter'. Declare a String 'msg', which will have 3 lines. The first line tells the user how many names were sorted and prints the integer 'number'. The second line reports on how many milliseconds were required to sort the names and prints the value 'timer.getElapsedTime()'. Finally, the third line reminds the user of the name of the output file. Print 'msg' with this call:
JOptionPane.showMessageDialog(null,msg);
My messageDialog looks like this:
StopWatch.java
This class implements a "stop watch" that allows you to time your program. This class is complete and you can use it as is.
Efficiency
Earlier it was mentioned that a bubble sort is not a very efficient algorithm for sorting. One way of studying the efficiency of a sort is to look at how long the sort takes to run. Specifically, we can look at how the sorting time changes as the number of elements that we sort changes. Try sorting 30, 100, 300, 1000, 3000, and 10,000 names, and each time make note of how many milliseconds are required to complete the sort. Then make an X-Y plot, with the number of elements sorted on the X-axis and millliseconds on the Y-axis. What shape of graph results? What does the graph say about the efficiency of the bubble sort?
Extra Credit
2 points
Modify the 'bubbleSort' method so that the outer loop is a WHILE loop. The WHILE loop should only continue to run as long as the ArrayList needs more sorting. How do you know when a bubble sort is done? If an array has, say, 100 elements, you could pass through the array 100 times. After 100 times through, the array would definitely be sorted. But what if the array is sorted after only 20 passes through the array? How would you know you don't have to do the other 80 passes? You could declare a boolean variable 'swapped'. Set 'swapped' to 'false' before beginning a pass through the array. When you do a swap during the bubble sort, set 'swapped' to 'true'. After passing through the entire array, check the value of 'swapped'. If it is 'true', you have more sorting to do. If it is 'false', no swaps were needed that time through the array, so the array is sorted and you can stop. You could use 'swapped' to control the process by putting 'swapped' inside the condition statement for the WHILE loop: while(swapped) { ... }
1 point
Adjust the 'bubbleSort' method so that the elements that are correctly positioned (the elements at the end of the ArrayList) are left alone during subsequent passes through the ArrayList.
You can download and run CompletedBubbleSort.jar to get an idea of how your program will when it is done. Before running the JAR file, also download BetelgeuseNames.dat and save it to the same folder that holds CompletedBubbleSort.jar.
You can download BubbleSort.java, BubbleSortTimer.java and StopWatch.java to use as starting points in writing your program. You will also need the input file BetelgeuseNames.dat.