## 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)