# Bubble sort

Bubble sort is a relatively dumb algorithm, which is in fact only used in the
academic world. It has no good properties, however, its process may remind you
of physical or natural phenomena. The algorithm works in waves, wherein each
wave it **drops the "heaviest" item over to the end** or sends the
lightest bubbles to the top (depending on the implementation). Each wave
compares a pair of neighboring items. If the left item is bigger than the right
one, it swaps the items. Thanks to this, the algorithm is stable.

## Possible improvements

The algorithm can be written in a completely stupid way using two nested for loops with a fixed number of iterations (both would run as many times as the items in the array). However, if we think about it a little we'd find out that it's pointless to compare the heaviest items at the "bottom" of the array because they already are in the right place. With this in mind, we can shorten the waves by 1 item continuously and even skip the very last one.

Another improvement might be to check if the array is already sorted (this
can easily happen). For example, imagine that we have a loop running and we no
longer need to sort it. We can easily set up a variable named
`swapped`

to `false`

and set this variable to
`true`

after each swap. If we get to the end of the loop and we
didn't swap anything (the variable has a value of `false`

), then we
know we're done. Those two improvements are shown in the preview in the source
code below.

The best possible implementation of this "bubbling" algorithm is called bi-directional bubble sort (or Shaker sort or Cocktail sort). There, it runs 2 waves in each run of the nested loop - one from left to right pushing heavier items down and another from the right pulling lighter items up. This removes the problem of so-called rabbits and turtles where rabbits are heavy items which quickly drop down. However, in the original implementation, lighter items come up very slowly.

## Algorithm properties

Time complexity | O (n^{2}) |
---|---|

Stability | Yes |

Speed | Very bad |

*Note: the time complexity is meant for average cases, and the speed is
like this when compared to all other sorting algorithms.*

## Process

Since Bubble sort is not an optimized algorithm, its process will be bit longer.

We have an array of the following items:

3 | 2 | 5 | 1 | 9 | 4 |

The first wave will go through the entire array and the greatest item will "bubble" over to the end.

3 |
2 |
5 |
1 |
9 |
4 |

Let's start up on the wave and compare the first 2 items (3 and 2):

3 |
2 |
5 |
1 |
9 |
4 |

Three is greater than two so we swap those items:

2 |
3 |
5 |
1 |
9 |
4 |

Then, we compare two more of the items (3 and 5):

2 |
3 |
5 |
1 |
9 |
4 |

Those are in the correct order, so we don't swap them. The wave continues...

2 |
3 |
5 |
1 |
9 |
4 |

2 |
3 |
1 |
5 |
9 |
4 |

2 |
3 |
1 |
5 |
9 |
4 |

2 |
3 |
1 |
5 |
4 |
9 |

After the first wave, the maximum (9) had bubbled up to the end, as expected. The last item is sorted in and we no longer have to deal with it. The next wave will be one item shorter than the previous wave and it'll bring the largest out of the array's unsorted parts to the end.

2 |
3 |
1 |
5 |
4 |
9 |

2 |
3 |
1 |
5 |
4 |
9 |

2 |
1 |
3 |
5 |
4 |
9 |

2 |
1 |
3 |
5 |
4 |
9 |

2 |
1 |
3 |
4 |
5 | 9 |

After the second wave, we're left with two sorted items at the end of the array. Let's do another wave.

2 |
1 |
3 |
4 |
5 | 9 |

1 |
2 |
3 |
4 |
5 | 9 |

1 |
2 |
3 |
4 |
5 | 9 |

1 |
2 |
3 |
4 | 5 | 9 |

Now, the array has been completely sorted. Realistically, the program would do one more wave before finding out that there is nothing to swap and return the result.

## Visualization

The author of the visualization widget is Jenkings

## Source code

public static void bubbleSort(int[] list) { int j = list.length - 2, temp; // swap check boolean swapped = true; while (swapped) { swapped = false; for (int i = 0; i <= j; i++) { // swapping if (list[i] > list[i + 1]) { temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; swapped = true; } } j--; } }

public static void bubbleSort(int[] list) { int j = list.Length - 2, temp; // swap check bool swapped = true; while (swapped) { swapped = false; for (int i = 0; i <= j; i++) { // swap if (list[i] > list[i + 1]) { temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; swapped = true; } } j--; } }

// sorts the array, assumes indexing from 0 procedure bubble_sort(var list: array of integer); var i, j, temp: integer; swapped: boolean; begin j:=length(list) - 2; // swap check swapped:=true; while swapped do begin swapped:=false; for i:=0 to j do // swap items if (list[i] > list[i + 1]) then begin temp:=list[i]; list[i]:=list[i + 1]; list[i + 1]:=temp; swapped:=true; end; dec(j); end; end;

# returns sorted array def bubble_sort(list) j = list.length - 2 # swap check swapped = true while (swapped) do swapped = false (j + 1).times do |i| # swap if (list[i] > list[i + 1]) temp = list[i] list[i] = list[i + 1] list[i + 1] = temp swapped = true end end j -= 1 end end