Bubble Sort

Average time complexity - O(n^2)

Best-Case time complexity - O(n)

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(1)

Bubble Sort is probably the simplest mainstream sorting algorithm. It is sometimes also known as Sinking Sort. While it has the same time complexity as Selection Sort, it is usually slower, because in the worst case it makes n^2 - n swaps between elements, whereas Selection Sort only makes n swaps even in the worst case. They both make the same number of comparisons.

It starts at the first index, compares it with the second index, and then swaps them if they are out of order. It then iterates through the entire array doing this. It makes multiple passes and just keeps swapping things until the array is sorted. However, each pass ends one element to the left of the previous. The first pass ends on the last element, the second pass ends on the element before the last, etc. This is because the greatest element inherently moves to the correct index on each pass.

For example, let's say we have array:

4, 1, 5, 2, 3

Bubble sort compares 4 and 1 (the first and second items). They are out of order, so it swaps them.

1, 4, 5, 2, 3

Now it compares the **second **and **third **elements (4 and 5). These are correct, so it moves on to the third and fourth (5 and 2). These are out of order, so it swaps them.

1, 4, 2, 5, 3

Now it compares the fourth and fifth (5 and 3), and they are out of order, so it swaps them.

1, 4, 2, 3, 5

The first pass is complete. Now it starts again at the beginning, but it ignores the last element because it knows it's in the correct place.

It compares the first two elements (1 and 4). They are correct, so it moves on to the second and third elements (4 and 2). These are out of order, so it swaps them.

1, 2, 4, 3, 5

Then it compares the third and fourth elements (4 and 3), and they are out of order, so it swaps them.

1, 2, 3, 4, 5

The array is now sorted, but Bubble Sort doesn't know that yet. So it continues on and makes one more pass. In efficiently implemented versions of Bubble Sort, the algorithm keeps track of whether it makes any swaps in a pass with a boolean value. If in any pass it makes no swaps, then the array is sorted, so it can stop making passes.