Selection Sort

Task: Sort this array in ascending order

for (int i = 0; i < n - 1; i++) {    int min = i;    for (int j = i + 1; j < n; j++) {        if (a[j] < a[min]) {            min = j;        }    }    if (min != i) {        swap(a, i, min);    }}

What you are watching

Selection sort walks the unsorted part of the array looking for the smallest value, remembers where it was, and swaps it into the boundary position once - at most one swap per pass, however long the array is. Sorting 29, 10, 14, 37, 13 takes four passes, and the third finds that the smallest remaining value is already in position, so no swap happens at all. The number of comparisons never changes with the input, which is why selection sort is quadratic even on an array that is already sorted.