Selection sort

Find the smallest remaining value and put it at the front of the unsorted part. Repeat.

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

Split the array into a sorted left part and an unsorted right part. Scan the right part for its minimum, then swap that minimum into position i.

Code

C++PythonC#

void selectionSort(vector<int>& a) {
    for (int i = 0; i < (int)a.size() - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < (int)a.size(); j++)
            if (a[j] < a[mn]) mn = j;
        swap(a[i], a[mn]);
    }
}

def selection_sort(a: list[int]) -> None:
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]: smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    # sorted in place

public static void SelectionSort(int[] a) {
    for (int i = 0; i < a.Length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.Length; j++)
            if (a[j] < a[min]) min = j;
        (a[i], a[min]) = (a[min], a[i]);
    }
}

Tips

Always n(n-1)/2 comparisons, even on sorted input.
At most n-1 swaps, which matters when writes are expensive. Not stable.

In the .NET library

Finding one minimum is a.Min() or Array.IndexOf(a, a.Min()). Selection sort is that step repeated n times.