Bubble, selection and insertion sort

Sorting means putting items in order. It makes searching fast (binary search), makes duplicates sit next to each other, and makes reports readable. The three simple sorts below are not what you use for a million items, but they teach the basic moves every sorting algorithm uses, and one of them is still used inside professional libraries.

Bubble sort

Walk through the array comparing neighbours and swap them if they are in the wrong order. After the first pass the largest value has “bubbled” to the end. Repeat on the rest. If a whole pass makes no swaps, the array is sorted and you can stop early.

1static void BubbleSort(int[] a)2{3    for (int pass = 0; pass < a.Length - 1; pass++)4    {5        bool swapped = false;6        for (int j = 0; j < a.Length - 1 - pass; j++)   // the last 'pass' items are done7        {8            if (a[j] > a[j + 1])9            {10                (a[j], a[j + 1]) = (a[j + 1], a[j]);11                swapped = true;12            }13        }14        if (!swapped) break;   // already sorted15    }16}

Selection sort

Find the smallest value in the unsorted part and swap it to the front of that part. Repeat. It always does the same number of comparisons, but at most n − 1 swaps, which helps when writing to memory is expensive.

1static void SelectionSort(int[] a)2{3    for (int i = 0; i < a.Length - 1; i++)4    {5        int min = i;6        for (int j = i + 1; j < a.Length; j++)7            if (a[j] < a[min]) min = j;8 9        if (min != i) (a[i], a[min]) = (a[min], a[i]);10    }11}

Insertion sort

Keep the left part sorted. Take the next value (the “key”), and shift bigger values one place right until you find the key’s spot, exactly like sorting playing cards in your hand.

1static void InsertionSort(int[] a)2{3    for (int i = 1; i < a.Length; i++)4    {5        int key = a[i];6        int j = i - 1;7        while (j >= 0 && a[j] > key)   // shift bigger values right8        {9            a[j + 1] = a[j];10            j--;11        }12        a[j + 1] = key;                // drop the key into the gap13    }14}15 16int[] data = { 5, 2, 8, 1, 9, 3, 7, 4 };17InsertionSort(data);18Console.WriteLine(string.Join(" ", data));

1 2 3 4 5 7 8 9

Comparing them

A sort is stable if items with equal keys keep their original order. Sort a beam schedule by profile with a stable sort and the beams within each profile stay in the order they were. Selection sort is not stable because its long-distance swap can jump an item over an equal one. Stability gets its own section in the .NET sorting lesson.

Why insertion sort still matters

Insertion sort does very little work when the data is nearly sorted: each item only shifts a short distance, so it approaches O(n). For tiny arrays it also beats the clever algorithms, because it has almost no overhead. That is why .NET’s Array.Sort switches to insertion sort for pieces of 16 elements or fewer.

1static void InsertionSortDescending(double[] a)2{3    for (int i = 1; i < a.Length; i++)4    {5        double key = a[i];6        int j = i - 1;7        while (j >= 0 && a[j] < key)   // was: a[j] > key8        {9            a[j + 1] = a[j];10            j--;11        }12        a[j + 1] = key;13    }14}15 16double[] lengths = { 4.5, 6.0, 3.0, 7.2, 6.0 };17InsertionSortDescending(lengths);18Console.WriteLine(string.Join(", ", lengths));

7.2, 6, 6, 4.5, 3