Bubble Sort

There are various ways of sorting a list, for example:

  • bubble sort
  • merge sort
  • shell sort
  • insertion sort
  • quick sort

The bubble sort is one method we can use to sort a list.

For example, we want to sort the list below:

1
12, 5, 7, 18, 11, 6, 12, 4, 17, 1

In this course we will look at the bubble sort and insertion sort (required by the AQA A-Level specification) and the quick sort (required by the OCR A-Level specificaton).

Here is the algorithm for the bubble sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Repeat
    X ← StartofArray
    Flag ← False
    Repeat
        If Number(X) > Number (X+ 1) Then
            Temp ← Number(X)
            Number (X) ← Number (X+ 1)
            Number(X+I) ← Temp
            Flag ← True
        End If
        X ← X+1
    Until EndofArray
Until Flag = False

Implementing a bubble sort in Python


Exercises

  1. Implement the bubble sort from the pseudocode. Follow the video if you need to.
  2. Extend your program by adding a counter to count the number of comparisons.
  3. Compare your count with the insertion sort (next page) to see which is the most efficient sort.