Bubble sort

Swap neighbours that are out of order. After each pass the largest remaining value has floated to the end.

Time O(n²)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Repeatedly sweep the array comparing adjacent pairs. Each sweep pushes the largest unsorted value into its final slot, so the next sweep can stop one position earlier.

Code

C++PythonC#

void bubbleSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

def bubble_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped: break
    # sorted in place

public static void BubbleSort(int[] a) {
    int n = a.Length;
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Tips

The swapped flag gives O(n) on already sorted input.
Stable and in place, but almost never the right choice in practice.

In the .NET library

Array.Sort and List<T>.Sort use introsort (quick sort, heap sort and insertion sort combined). You only write bubble sort in interviews.