Home CPSC 340

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 two changes:

  1. 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.
  2. 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.

Next run the programs with different input sizes to complete the following chart:

NBubble SortMerge Sort
1000
5000
10000
20000
30000
40000
50000
60000
70000
100000---
200000---
300000---
400000---
500000---
600000---
700000---
800000---
900000---
1000000---

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

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


 

Submitting

When you're done, email your graph to ifinlay@umw.edu.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.