The goal for this exercise is to measure the performance of Bubble Sort. The longer-term goal is set you up to compare this performance to other, alternative algorithms (such as selection sort, QuickSort, MergeSort, HeapSort, etc) so that you will have a clear understanding of why the Big O notation is useful.
What you need to do to prepare for this exercise:
Much like you did with the two searching methods, you're now going to instrument your sorting method so that you
can measure it's performance. Copy the code you wrote in the previous exercise, and name it BubbleSortPerfMeasured.
It should take the extra, out parameter numSwaps, much like the other "PerMeasured" methods
do. When this BubbleSort starts, it should initialize that variable to be zero. It should increment (increase
by one) that parameter each time it swaps any two elements. You should also provide
a second out parameter, that gets incremented each time it compares any two elements (regardless of whether it swaps them or not). We’ll be collecting up both these sets of information because the
number of comparisons is a good measure of how much work the algorithm is doing overall, and the number of swaps
is a more specific indicator of exactly how much work this algorithm is doing (especially if you want to compare
the efficiency of this algorithm to a similar sorting algorithm, such as Selection Sort)
So BubbleSortPerfMeasured was given the following array, and was asked to sort it into ascending order, it would
set numSwaps to be 1 (since you'd need to swap the 6 & the 10 once, in order to end up with
a sorted array), and numComparisons to be 2 (because the unoptimized outer loop executes twice).
| Index: 0 | Index: 1 |
|---|---|
| Value: 10 | Value: 6 |
Alternately, if the array looked like this:
| Index: 0 | Index: 1 |
|---|---|
| Value: 6 | Value: 10 |
you'd still have numComparisons being 2, but numSwaps would be 0, since it had never swapped
anything.
Once you’ve done that, you should test the function on your own.
Implement the BubbleSortPerfMeasured method, within the SearchingAndSorting class.
Make sure that your method can handle being passed a null parameter for the array. In this case, you can simply zero out the comparison / swap counters and then return.
Note that you don't (technically) need to complete the "BubbleSort" exercise in this same lesson – you can jump straight to this exercise. However, many people find it easier to do that exercise first, then copy-and-paste that code into this exercise.