Home CPSC 340

Lab 7: Sort Comparison

Objective

To practice timing programs and explore the difference between bubble sort and merge sort.

Task

For this lab you will experiment with the bubble sort and merge sort programs presented:

To begin, download the programs, and then make three changes to both programs:

Delete the lines of code that print out the arrays. That will only slow the programs down and interfere with testing the speed of sorting.
Change the programs so that instead of having an array size of 25, the size is taken in the command line argument args[0]. This will make it easier to test different sizes, since we won't need to recompile.
Add code to the program so it prints out how long the program takes to run. You can see these instructions to review how to do this.

In this lab you will be filling out the following chart and comparing three different variants of our sorting program:

N	Bubble Sort	Optimized Bubble Sort
1000
5000
10000
20000
30000
40000
50000
60000
70000
100000
200000
300000	N/A	N/A
400000	N/A	N/A
500000	N/A	N/A
600000	N/A	N/A
700000	N/A	N/A
800000	N/A	N/A
900000	N/A	N/A
1000000	N/A	N/A

Part 1: Bubble Sort

For this, you should be able to run the bubble sort program (with the three changes listed above), and record your times. If the program does not begin to slow down substantially as you get to 200000, then you probably messed up one of the changes!

Do not bother running bubble sort for inputs greater than 200,000 as it will just take too long.

Part 2: Bubble Sort Optimization

Next, make the optimization we briefly discussed to the bubble sort program. In this optimization we stop early in for loop and don't go all the way to the end (because each pass puts the biggest item left in place).

To do this, we will change the following line:


    for (int i = 0; i <= array.length - 2; i++) {

Instead of subtracting 2, make a new variable to subtract by. Start that variable off equal to 2, but add 1 to it after each pass. That will cause the for loop to go one iteration less each time we run it.

Run the bubble sort experiment again, and record the time the program takes now. If you did things right, it should be just a tad faster.

Part 3: Merge Sort

Now run the merge sort program and fill in that column of the graph. You should be able to go all the way to 1000000 this time, as the program should be substantially faster.

The lesson here is algorithmic improvements that give a better Big-O are way more important than smaller optimizations like the one we made to bubble sort!

Submitting

Finally make a graph (using Excel, Google Sheets, or similar program) of the time taken by the three programs relative to the input size. Does the bubble sort graph look like a parabola? How much better is the optimized version? How much better does merge sort scale?

When you're done, submit your table and graph under the lab assignment in Canvas.