bubble-sort

课 Progress

0% Complete

Bubble sort

In A Level Computer Science, a bubble sort sorts items into order, smallest to largest
It compares pairs of elements and swaps them if they are out of order
The first element is compared to the second, the second to the third, the third to the fourth and so on, until the second to last is compared to the last. Swaps occur if each comparison is out of order
This overall process is called a pass

The highest value in the list eventually “bubbles” its way to the top like a fizzy drink, hence the name “Bubble sort”

Once the end of the list has been reached, the value at the top of the list is now in order and the sort resets back to the start of the list. The next largest value is then sorted to the top of the list
More passes are completed until all elements are in the correct order
A final pass checks all elements and if no swaps are made then the sort is complete
An example of using a bubble sort would be sorting an array of names into alphabetical order, or sorting an array of student marks from a test

Figure 1: Performing the Bubble sort

To determine the algorithm’s execution time as measured by the number of instructions or steps carried out Big-O notation must be used
Four statements are present in the above algorithm O(1), followed by a while loop O(n) containing two statements and a further for loop O(n). This results in the expression: 2n² + 4
As coefficients and lower order values are not used, this give the bubble sort O(n²) worst case time complexity
The best case scenario would be an already sorted list which means a time complexity of O(n) as each item must still be compared to check if they are in order
The average case scenario would be an almost sorted list leading to O(n²/2), which if coefficients are removed still gives O(n²)

A bubble sort has a space complexity of O(1) because it operates in-place, requiring a fixed amount of memory
The fixed amount of memory is for variables such as loop counters and a temporary swap variable

The trace table follows the algorithm through, updating values that change in the table
Each iteration of the list reduces the overall size of the list by 1 as after each pass the previously sorted final digit is in order and does not need to be rechecked. This means that 9 is in order and doesn’t need to be rechecked, followed by 9 and 7, followed by 9, 7 and 6 and so on
When the if statement is checked a new row has been added to show the swap of list[j], list[j + 1] and Temp, followed by the subsequent change to Swap from FALSE to TRUE
After several iterations (that are not shown) the algorithm will eventually output a sorted list

Trace table of the bubble sort