Bubble Sort Topic 4.3.15 / Core / 2 lessons
Key points
  • implementing a bubble sorting algorithm;
  • tracing a bubble sorting algorithm.
Vocabulary
  • bubble sort;
  • traverse;
  • flag.
Resources
  • Eck chapter 8.4
Related topics

Starter

Sorting the more arbitrary way:

Is this sorting into order or into categories?

Tasks
  1. Follow through this presentation on bubble sorts.
  2. BubbleSort1. Examine this Java code for a single pass through an array to be sorted. Note that the only effect is to bring the highest value to the top.
  3. BubbleSort2 shows nesting to allow as many passes as there are elements.
  4. Look carefully at the results for BubbleSort2 and consider ways of making the algorithm more efficient. There is no point continuing the sort if everything is in place - the computer will not know to stop without a test for it in the code and so would spend just as long "sorting" a perfectly ordered array as it would a jumbled one. Here, a boolean variable called swapped (known as a flag) is used to keep track of whether anything was swapped on the last pass through the array. If it was not, all are in order and the sorting can terminate early. See BubbleSort3 here.
  5. Since the first pass bubbles the largest to the top, there is no need to check the top value on the second pass. Similarly for the second largest on the third pass, etc. This version stops the pass through the array one short each time, saving processor time. Here is BubbleSort4.
  6. ArrayBubbleSort shows the bubble sort technique in action on a larger array.