# Sorting Algorithms And Big O Notation Efficiency

07 Jul 2020

## Bubble Sort

Bubble sort is a basic sorting algorithm, which starts by pointing at two consecutive items in an array (starting at the beginning two elements of an array), then compares the first item with the second one. If the two items are out of order (the left value is greater than the right value), swap them, or do nothing if they are in the right order.

Then the pointers are moved one cell to the right and the same comparisons and swaps are made until the end of the array has been reached, and then we repeat this entire process until we can get to the end of the array without making any swaps (when it has been fully sorted).

The sequence of moving the pointers, making a comparison and swapping is known as a passthrough, where we have "passed through" the primary steps of the algorithm and will repeat the same process until the array is fully sorted.

Steps to sorting the following array:

`val list = mutableListof(4,2,7,1,3)`

## Passthrough 1

- Point to index 0 and 1
- Compare values at index 0 and 1 (4 is greater than 2)
- Swap index 0 (4) with index 1 (2)
`2,4,7,1,3`

- Point to index 1 and 2
- Compare values at index 1 and 2 (4 is not greater than 7)
- Do nothing
- Point to index 2 and 3
- Compare values at index 2 and 3 (7 is greater than 1)
- Swap index 2 (1) with index 3 (7)
`2,4,1,7,3`

- Point to index 3 and 4
- Compare values at index 3 and 4 (7 is greater than 3)
- Swap index 3 (7) with index 4 (3)
`2,4,1,3,7`

The largest number in the array (7) has bubbled all the way to the end of the array with this passthrough, which is why this is called a bubble sort.

At the end of this pass through, we swapped values at least once, which means that we need to do another passthrough until the array has been sorted fully (no more swaps).

## Passthrough 2

`2,4,1,3,7`

- Point to index 0 and 1
- Compare values at index 0 and 1 (2 is less than 4)
- Do nothing
- Point to index 1 and 2
- Compare values at index 1 and 2 (4 is greater than 1)
- Swap index 1 (4) with index 2 (1)
`2,1,4,3,7`

- Point to index 2 and 3
- Compare values at index 2 and 3 (4 is greater than 3)
- Swap index 2 (4) with index 3 (3)
`2,1,3,4,7`

- We don't have to compare the last two indices, because we know that 7 is already in the right place.

We swapped values at least once this time through, so another passthrough is needed.

## Passthrough 3

`2,1,3,4,7`

- Point to index 0 and 1
- Compare values at index 0 and 1 (2 is greater than 1)
- Swap index 0 with index 1
`1,2,3,4,7`

- We know that 3, 4 and 7 are in the right place, so don't need to do any more comparisons.

We swapped values at least once this time through, so another pas sthrough is needed.

## Passthrough 4

`1,2,3,4,7`

- Point to index 0 and 1
- Compare values at index 0 and 1 (1 is less than 2)
- Since the first two indices are now in the right order, and we know that everything else has been sorted correctly, we can stop sorting here.

Our list has been successfully sorted using the bubble sort method.

```
def bubble_sort(list):
unsorted_until_index = len(list) - 1
sorted = False
while not sorted:
sorted = True
for i in range(unsorted_until_index):
if list[i] > list[i+1]:
sorted = False
list[i], list[i+1] = list[i+1], list[i]
unsorted_until_index = unsorted_until_index - 1
list = [65, 55, 45, 35, 25, 15, 10] bubble_sort(list)
print list
```

- We keep track of up to which index is still unsorted with
`unsorted_until_index = len(list) -1`

. At the beginning, the array is totally unsorted, so we initialize this variable to be the final index in the array. - We also create a
`sorted = False`

variable which allows us to keep track whether the array is fully sorted. When we first run the code, it isn't - We begin a while loop that will last as long as the array is not sorted. Next, we preliminarily establish sorted to be True, but will change this back to False as soon as we make any swaps.
- Withing the while loop, we begin a for loop that starts from the beginning of the array and goes until the index that has not been sorted yet. Within this loop, we compare every pair of adjacent values, and swap them if they're out of order. We also change sorted to false if we make a swap.
- At the end of the sorted array
`unsorted_until_index = unsorted_until_index - 1`

, we can assume that the value we've bubbled up to the right is now in its correct position. Because of this, we decrement the unsorted_until_index by 1, because it has now been sorted. - Each round of the while loop represents another passthrough, and we run it until we know our array has been fully sorted.

## The efficiency of Bubble Sort

The bubble sort contains two kinds of steps:

- Comparisons: Two numbers are compared with each other to determine which is greater.
- Swaps: Two numbers are swapped with one another in order to sort them.

We'll start by determining how many comparisons take place in Bubble Sort.

If an array has five elements, we have to make four comparisons between 2 sets of numbers. In our second passthrough, we only had to make 3 comparisons because we didn't have to compare the final two numbers. In our third passthrough, we made 2 comparisons and in our fourth passthrough we made just one comparison.

4 + 3 + 2 + 1 = 10 comparisons

To make it more general, we'd say that for N elements, we make (N - 1) + (N - 2) + (N - 3) ... + 1 comparisons.

In terms of the swaps, in a worst-case scenario, where the array is not just randomly shuffled, but sorted in descending order (the exact opposite of what we want), we'd actually need a swap for each comparison. So we'd have 10 comparisons and 10 swaps in such a scenario for 20 swaps.

With an array containing ten elements in reverse order, we'd have:

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparisons, and another 45 swaps, a total of 90 steps. With an array of twenty elements, we'd have 190 comparisons and approx 190 swaps, for a total of 380 steps.

As the number of elements increase, the number of steps grows exponentially.

The pattern of growth suggests that as N increases, the steps increase by approximately N2

In Big O Notation, we would say that Bubble Sort has an efficiency of O(N^{2}), also referred to as *quadratic time*.

O(N^{2})

^{2}) alarm bells should start going off in your head.