Bubble sort

Overview

Recall questions on how bubble sort works and why it is named so, tracing passes, shortening passes, the swap flag optimisation, best, average and worst-case and space complexity, comparison counts, and why it is slower than insertion sort.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe how a bubble sort works, step by step.

   Model answer

   Start at the beginning of the list and compare the first two items; if they are in the wrong order, swap them. Move along one position and compare the next pair, continuing to the end of the list. That is one pass, and it guarantees the largest remaining item has been carried to the end. Repeat the passes over the unsorted part of the list until a whole pass is completed with no swaps, at which point the list is sorted.

2. 2

   Trace a bubble sort on the list 5, 1, 4, 2, showing each pass.

   Model answer

   Pass 1: compare 5 and 1 and swap, giving 1, 5, 4, 2; compare 5 and 4 and swap, giving 1, 4, 5, 2; compare 5 and 2 and swap, giving 1, 4, 2, 5. Pass 2: compare 1 and 4, no swap; compare 4 and 2 and swap, giving 1, 2, 4, 5. Pass 3: with the bound shrinking again only 1 and 2 are compared, no swap is made, and because a whole pass passed without a swap the sort stops. The sorted list is 1, 2, 4, 5.

3. 3

   After one complete pass of a bubble sort, what can you be certain of?

   Model answer

   That the largest value in the list is now in its final position at the end. Any comparison it takes part in results in a swap, so once the pass reaches it, it is carried all the way to the end. Nothing else is guaranteed to be in its final place.

4. 4

   Why can each pass of a bubble sort be shorter than the one before?

   Model answer

   Because each completed pass fixes one more item at the end of the list. After k passes the last k items are known to be correct, so the next pass need only run over the first n minus k items, saving a growing number of pointless comparisons.

5. 5

   Describe the optimisation that lets a bubble sort stop early.

   Model answer

   Keep a Boolean flag that is set to false at the start of every pass and set to true whenever a swap is made. At the end of the pass, if no swap was made, then no pair was out of order, so the whole list must be sorted and the algorithm stops immediately instead of completing the remaining passes.

6. 6

   What is the best-case complexity of bubble sort, and what exactly does it depend on?

   Model answer

   O(n), but only for the optimised version that uses a swap flag, and only when the list is already sorted. That version makes a single pass of n minus 1 comparisons, finds no swaps and stops. Without the flag the algorithm has no way of knowing the list is sorted and grinds through every pass anyway, making even the best case O(n squared).

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.