Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. It examines all pairs of adjacent elements, swapping them when they are out of order.

Bubble Sort

Algorithm :

for i in 0 .. n-2
    for j in i .. n-1
        if (a[j] > a[j+1]) swap(a[j], a[j+1]) 

We need to stop when we make a pass that doesn’t swap anything.

for i in 0 .. n-2
    swapped := false
    for j in i .. n-1
        if (a[j] > a[j+1])
            swap(a[j], a[j+1])
            swapped := true
    return if not swapped 

Example :

30 64 26 46 109 21 84 98
30 26 46 64 21 84 98 109
26 30 46 21 64 84 98 109
26 30 21 46 64 84 98 109
26 21 30 46 64 84 98 109
21 26 30 46 64 84 98 109
21 26 30 46 64 84 98 109

When no swaps that means input is sorted now.

Notes :

1. O(N^2) time complexity in worst, and average cases.
2. O(N) time complexity in best case if input is already sorted or nearly sorted.
3. Exchanges only adjacent elements, which is really slow.
4. It is stable and in-place sorting algorithm.
5. Best case swaps is O(1), and worst case is O(N^2)
6. Best case comparisons is O(N), and worst case is O(N^2)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.