Sorting algorithms

Overview

Recall questions on bubble sort and merge sort, the effect of the swap flag, their time complexities, and how the running time grows as the list gets longer.

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 the bubble sort algorithm.

   Model answer

   Work through the list from the start, comparing each adjacent pair of items and swapping them if they are in the wrong order. At the end of one such pass the largest remaining item has moved to the end of the unsorted section, so the next pass need not examine it. Repeat the passes until a whole pass takes place with no swaps, at which point the list is sorted.

2. 2

   Trace a bubble sort of the list [5, 1, 4, 2], sorting into ascending order.

   Model answer

   Pass 1: compare 5 and 1, swap, giving [1, 5, 4, 2]; compare 5 and 4, swap, giving [1, 4, 5, 2]; compare 5 and 2, swap, giving [1, 4, 2, 5]. The largest value, 5, is now in place. Pass 2: compare 1 and 4, no swap; compare 4 and 2, swap, giving [1, 2, 4, 5]. Pass 3: with the bound shrinking again, only 1 and 2 are compared, no swaps at all, so the list is sorted: [1, 2, 4, 5].

3. 3

   Why is a bubble sort called a bubble sort?

   Model answer

   Because on each pass the largest remaining value moves steadily to the end of the list, and the smaller values gradually rise towards the front — the values 'bubble' up to their correct positions one place at a time.

4. 4

   How does the swap flag improve a bubble sort?

   Model answer

   A boolean variable is set to false at the start of each pass and to true whenever a swap is made. If a whole pass completes with the flag still false, no two adjacent items were out of order, so the list must already be sorted and the algorithm can stop immediately rather than continuing with pointless passes. This makes the best case, an already-sorted list, take a single pass.

5. 5

   What is the time complexity of a bubble sort?

   Model answer

   O(n²). There are up to n - 1 passes and each pass makes up to n - 1 comparisons, so the number of comparisons grows with the square of the number of items — roughly n(n-1)/2 in total. Doubling the length of the list therefore quadruples the time taken.

6. 6

   What is the best case for a bubble sort, and what condition does it require?

   Model answer

   O(n), when the list is already sorted, because a single pass makes n - 1 comparisons, performs no swaps, and the swap flag then stops the algorithm. This best case only applies to the version that uses a swap flag; without one the algorithm always performs its full set of passes and is O(n²) whatever the data.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.