C++ Notes: Algorithms: Selection Sort

Selection sort makes n-1 passes over the data, finding the largest remaining value on each pass. A common optimization is that the index of the potentially largest element is saved, so that at the end of a pass, an exchange (swap) only needs to be done once.

Example

void selectionSort(int x[], int n) {
    for (int pass=0; pass<n-1; pass++) {
        int potentialSmallest = pass;  // assume this is smallest

        //--- Look over remaining elements to find smallest.
        for (int i=pass+1; i<n; i++) {
            if (x[i] < x[potentialSmallest]) {
                //--- Remember index for latter swap.
                potentialSmallest = i;
            }
        }
        
        //--- Swap smallest remaining element
        int temp = x[pass];
        x[pass] = x[potentialSmallest];
        x[potentialSmallest] = temp;
    }
}