Bubble sort

Overview

How a bubble sort works and purpose of a swap flag in a bubble 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.

   Model answer

   A bubble sort compares each adjacent pair of items and swaps them if they are in the wrong order. Repeated passes are made until a pass produces no swaps.

2. 2

   Why is the algorithm called a bubble sort?

   Model answer

   The largest value moves to the end of the list on the first pass, as though it bubbles to the surface. Each later pass carries the next largest value into place.

3. 3

   A bubble sort is applied to the list 7, 3, 9, 2, 8, 5. What is the list after the first pass?

   Model answer

   The list reads 3, 7, 2, 8, 5, 9 after the first pass. The value 9 has reached its final position at the end.

4. 4

   State the list 7, 3, 9, 2, 8, 5 after the second pass of a bubble sort.

   Model answer

   The list reads 3, 2, 7, 5, 8, 9 after the second pass. The two largest values 8 and 9 are now in place.

5. 5

   Working on 7, 3, 9, 2, 8, 5, how many passes does a bubble sort with a swap flag make in total?

   Model answer

   The sort makes four passes in total. Three passes change the list and the fourth makes no swaps, which stops the algorithm.

6. 6

   How many comparisons does a bubble sort make on a list of six items if the range shortens by one after each pass?

   Model answer

   The comparisons total 15, from 5 + 4 + 3 + 2 + 1. The general formula is n(n − 1) ÷ 2.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.