Algorithm for an exchange sort

Bubble sort is an exchange sort. It repeatedly compares adjacent elements and exchanges them if they are out of order. After each pass the largest remaining element "bubbles" to the end.

Algorithm

BubbleSort(a[0..n-1])
1. for pass = 1 to n-1
2.     swapped = 0
3.     for i = 0 to n-pass-1
4.         if a[i] > a[i+1]: swap a[i], a[i+1]; swapped = 1
5.     if swapped = 0: stop     (already sorted)

C code

void bubble_sort(int a[], int n) {
    int pass, i, t, swapped;
    for (pass = 1; pass < n; pass++) {
        swapped = 0;
        for (i = 0; i < n - pass; i++) {
            if (a[i] > a[i + 1]) {          /* exchange */
                t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;                /* no exchange: sorted */
    }
}

Trace for 5 3 8 1

Complexity: worst and average O(n²), best O(n) (already sorted, with the swapped flag). It is stable and in-place, using O(1) extra space.