Bubble Sort: Big Ones Float Up

Why sort at all?

Sorted data is easier to use: binary search needs it, finding duplicates becomes “look at your neighbour”, and the smallest and biggest are at the ends. Sorting is one of the most common steps in real programs.

The idea

Walk along the array comparing neighbours. If a pair is in the wrong order, swap it. After one full pass the biggest value has “bubbled” to the end. Repeat for the rest.

Think of it like this: Kids lining up by height: each kid compares with the one next to them and they swap if needed. The tallest kid ends up at the back after one walk down the line.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8};
        for (int pass = 1; pass < a.length; pass++) {
            boolean swapped = false;
            for (int i = 0; i < a.length - pass; i++) {   // the last 'pass' items are done
                if (a[i] > a[i + 1]) {
                    int tmp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = tmp;
                    swapped = true;
                }
            }
            System.out.println("after pass " + pass + ": " + Arrays.toString(a));
            if (!swapped) break;                          // nothing moved: already sorted
        }
    }
}

Output

after pass 1: [1, 4, 2, 5, 8]
after pass 2: [1, 2, 4, 5, 8]
after pass 3: [1, 2, 4, 5, 8]

The swapped flag is a nice touch: on an already sorted array bubble sort stops after one pass, O(n). In general it's O(n²).