Bubble Sort (OCR A Level Computer Science)

Bubble sort

What is a Bubble Sort?

• A Bubble Sort sorts items into order, smallest to largest, by comparing pairs of elements and swapping 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

• 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

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² + 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²)

Space Complexity of the Bubble Sort

• As the bubble sort requires no additional space, it is space complexity O(n), where n is the number of items in the list

Tracing a Bubble Sort

• 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

Implementing a Bubble Sort

Pseudocode

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)

• The algorithm above implements an efficient bubble sort in that with each successive iteration, the number of comparisons decreases

  • This is due to the sorted end of the list not being rechecked as it is already sorted and therefore inefficient to compare them 

  • This is managed by the j for loop where i increments after each iteration and reduces the number of compared items by 1 

  • This is because the last iteration’s sorted element should already be in the correct position. The overall effect is reducing unnecessary swaps

• Furthermore, using a while loop instead of a for loop means that if a swap does not occur then the list is in order. A for loop would continue comparing even if the items are already in order

Python

def bubble_sort(list):
    n = len(list)
    for i in range(n - 1):
        swapped = False
        for j in range(0, n - i - 1):
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
                swapped = True
        if not swapped:
            break  # Early termination if no swaps occurred
    return list

Java

public class BubbleSort {
    public static void bubbleSort(int[] list) {
        int n = list.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (list[j] > list[j + 1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;  // Early termination if no swaps occurred
            }
        }
    }