27-07-2012, 02:12 PM
Bubble Sort & Merge Sort
Bubble Sort.ppt (Size: 680.5 KB / Downloads: 19)
"Bubbling Up" the Largest Element
Traverse a collection of elements
Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping
Items of Interest
Notice that only the largest value is correctly placed
All other values are still out of order
So we need to repeat this process
Repeat “Bubble Up” How Many Times?
If we have N elements…
And if each time we bubble an element, we place it in its correct location…
Then we repeat the “bubble up” process N – 1 times.
This guarantees we’ll correctly place all N elements.
Already Sorted Collections?
What if the collection was already sorted?
What if only a few elements were out of place and after a couple of “bubble ups,” the collection was sorted?
We want to be able to detect this and “stop early”!
Using a Boolean “Flag”
We can use a boolean variable to determine if any swapping occurred during the “bubble up.”
If no swapping occurred, then we know that the collection is already sorted!
This boolean “flag” needs to be reset after each “bubble up.”