# 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;
        }
    }