## Sorting Algorithms: Bubble Sort

Bubble the larger value to the top on each iteration.

- Loop through the array
- At each index, if current index is larger than next index, then swap them
- After looping through the array, the largest value should have bubbled to the end (dont have loop over that again)
- Repeat the above steps until sorted

Efficiency notes:

- After each iteration the highest value has bubbled up into its place and therefore do not have to iterate over it again. ie keep a pointer of where the last iteration ended and reduce it by one each time
- If you have passed through the enitre set of data without swapping once then the data is sorted and you do not have to continue.

## Example

Let's sort an array of ints as an example: [ 5, 2, 1, 4, 3 ]

### Iteration 1:

pointer = 4 (last index)

- i = 0 [ 5, 2, 1, 4, 3 ] (swap 5 Á 2)
- i = 1 [ 2, 5, 1, 4, 3 ] (swap 5 Á 1)
- i = 2 [ 2, 1, 5, 4, 3 ] (swap 5 Á 4)
- i = 3 [ 2, 1, 4, 5, 3 ] (swap 5 Á 3)
- i = 4 [ 2, 1, 4, 3, 5 ] (bubbled to top)

### Iteration 2:

pointer = 3 (-1 from previous)

- i = 0 [ 2, 1, 4, 3, 5 ] (swap 2 Á 1)
- i = 1 [ 1, 2, 4, 3, 5 ] (do nothing)
- i = 2 [ 1, 2, 4, 3, 5 ] (swap 4 Á 3)
- i = 3 [ 1, 2, 3, 4, 5 ] (bubbled to top)

### Iteration 3:

pointer = 2 (-1 from previous)

- i = 0 [ 1, 2, 3, 4, 5 ] (do nothing)
- i = 1 [ 1, 2, 3, 4, 5 ] (do nothing)
- i = 2 [ 1, 2, 3, 4, 5 ] (do nothing)

no swap happened this iteration therefore complete algorithm

## About the bubble sort algorithm

Big O notation: O(n^{2}) because the outer loop runs n times & the inner loop runs n timesat worst case

Is Data sensitive: the erlier the data is ordered then the earlier completes eg if data is already order then it wil only iteration once O(n) Worst case: reverse ordered list

High data movement: requires many data swaps per iteration

In-place sort: the sorted items occupy the same storage as the original ones

Stable sort: Duplicates remain in their original order