Lesson 05: Bubble Sort
Specification Points Addressed in this lesson:
- Understand and explain how the bubble sort algorithm works.
1. Bubble Sort
The bubble sort is one of the most straightforward sorting algorithms to explain and code. The algorithm is outlined below:
- Start at the beginning of the list
- Compare adjacent items; if they are out of order, then swap them
- Keep comparing adjacent items for the entire list (one pass)
- Do more passes until no swaps are made in a pass
This is the pseudo-code for the bubble sort algorithm.
SUBROUTINE bubbleSort() swap ← TRUE WHILE (swap) swap ← FALSE FOR i ← 0 TO LEN(array) -1 IF (array[i] > array[i+1]) THEN temp ← array[i] array[i] ← array[i+1] array[i+1] ← temp swap ← TRUE ENDIF ENDFOR ENDWHILE ENDSUBROUTINE
The algorithms first create a boolean variable called swap and assign the value TRUE to the variable. This is then followed by a WHILE loop with a condition of swap. Since swap was assigned to TRUE, the WHILE loop must be executed at least once.
In the WHILE loop, swap is immediately assigned to FALSE; then, a FOR loop is used to iterate over the list and compare adjacent elements. If the elements are out of order, they are swapped around with the help of a variable called temp. Once a swap is made, the variable swap is reassigned to TRUE – to ensure that the WHILE loop is repeated at least once more.