Basic Sorting Algorithms: Bubble vs Insertion

Explanation


Bubble Sort: Repeatedly loops through the list, comparing each pair of adjacent items and swapping them if needed, until it is sorted
Insertion Sort: Builds a sorted list by comparing the next unsorted item with each item of the sorted list and inserting it at the appropriate place (initially, the sorted list consists of only the first item of the list)

Performance Comparison

As you can see, their performance are identical for best-case, worst-case and average-case scenarios. The only difference is that insertion sort performs better for a substantially sorted list with very few inversions.

Type Best-case performance Worst-case performance Average-case performance
Bubble O(n) for an already sorted list O(n^2) for a list sorted in reverse O(n^2)
Insertion O(n) for an already sorted list O(n^2) for a list sorted in reverse O(n^2)

Compared with most other algorithms, like quicksort, both bubble sort and insertion sort fall short on worst-case and average-case performance. However, they do have the fastest performance for an already sorted list.

Therefore, bubble sort is often avoided as the only advantage it possesses is shared with insertion sort - which has a better performance for substantially sorted lists.

Code Example (in Python)


Bubble Sort

unsorted = [1, 5, 2, 3, 10, 7, 8]	#unsorted array of numbers

def bubble(toSort):
    needsSwap = TRUE
    while needsSwap:
        needsSwap = FALSE
        for i in range(1, len(toSort)):
            if toSort[i-1] > toSort[i]:
                toSort[i-1], toSort[i] = toSort[i], toSort[i-1]
                needsSwap = TRUE
    return toSort

Line 4-5: start a while loop that ends when needsSwap becomes FALSE
Line 6: set needsSwap to FALSE, because no swapping has occurred at this point
Line 7-9: step through the list with a for loop, comparing each adjacent pair of items and if the first item is larger than the second, swap the two
Line 10: if there has been any swapping, set needsSwap to FALSE and the loop starts over

Insertion Sort

unsorted = [1, 5, 2, 3, 10, 7, 8]	#unsorted array of numbers

def insertion(toSort):
    currentPosition = 1
    while currentPosition < len(toSort):
        i = currentPosition
        while i > 0 and toSort[i-1] > toSort[i]:
            toSort[i-1], toSort[i] = toSort[i], toSort[i-1]
            i -= 1
        currentPosition += 1
    return toSort

Line 4: set currentPosition to 1 which is the second element of the array
Line 5: stay in a while loop until currentPosition is at the end of the array
Line 6: set index i to the current position number
Line 7-9: compare the value of the current position toSort[i] with the previous item and swapping them if the previous item is larger, until tosort[i] is larger than its previous item or it is at the start of the list
Line 10: increment currentPosition, the comparison starts over for the next item on the unsorted list



A Level Computer Science Syllabus


AS Requirement:

  • write algorithms/program code to process array data including:
    • sorting using a bubble sort

A2 Requirement:

  • write an algorithm to implement an insertion sort
  • write an algorithm to implement a bubble sort

(Updated for the 2017-2019 CIE Syllabus)

Show Comments