Bubble Sort

What is a bubble sort?

• 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

Examiner Tips and Tricks

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 order

Performing the bubble sort

Figure 1: Performing the Bubble sort

Time complexity of 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^2+4$
• As coefficients and lower order values are not used, this give the bubble sort $O(n^2)$ 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/2)$, which if coefficients are removed still gives $O(n^2)$

Space complexity of the bubble sort

• 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

Tracing a bubble sort

• Shrinking Search Space: After each full pass, the largest unsorted element reaches its final position. This means the algorithm can ignore one additional element at the end of the list with every new pass.
• Tracking Swaps: A boolean flag (swap) is used to monitor if any changes were made. If a full pass occurs without a single swap, the list is already sorted, and the algorithm can terminate early.
• State Changes: The trace table updates whenever an index is compared and whenever a temp variable is used to facilitate a swap.

Pass	Index (j)	list[j]	list[j+1]	Swap Needed?	Temp	Swap Flag
1	0	5	9	No (5 < 9)	-	False
1	1	9	4	Yes (9 > 4)	9	True
1	2	9	2	Yes (9 > 2)	9	True
1	3	9	6	Yes (9 > 6)	9	True
…	…	…	…	…	…	…
2	0	4	5	No (4 < 5)	-	False
2	1	5	2	Yes (5 > 2)	5	True

Implementing a Bubble Sort

list = [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]
last = len(list)
swap = True
i = 0
while i < (last - 1) and (swap = True)
	swap = False
	for j = 0 to last - i - 2
		if list[j] > list[j+1]
			temp = list[j]
			list[j] = list[j+1]
			list[j+1] = temp
			swap = True
		endif
	next j
	i = i + 1
endwhile
print(list)

• Optimised Comparisons: The algorithm is efficient because the inner loop range decreases with every pass (last - i - 2). Since the largest items are locked into place at the end of the list, there is no need to re-check them.
• Early Termination: By using a while loop combined with a swapped flag, the algorithm can recognize if a list is sorted mid-way through. If the inner for loop completes without making a single swap, the list is confirmed to be in order, and the function returns immediately.
• Memory Efficiency: Bubble sort is an “in-place” algorithm, meaning it requires very little extra memory (only a single temp variable) to perform the sort, regardless of the list size.
• The Swap Logic: The temp variable is essential to prevent data loss. It holds the value of list[j] so that list[j+1] can be moved into its spot without overwriting the original value.

def sort(data):
	swapped = True # start the outer loop
	while swapped: # keep looping while we made a swap
		swapped = False # assume this pass will be swap‑free
		for i in range(len(data) - 1):
			if data[i] > data[i + 1]:	
				# --- swap ---
				temp = data[i]  
				data[i] = data[i + 1]  
				data[i + 1] = temp
				swapped = True
	return data