Selection Sort

Description

Assuming there are N data items to sort, this algorithm steps through the data set N times (in other words, makes N passes). In each pass, it finds the next smallest (or largest) item and swaps it with the first (or last) item that hasn't been sorted yet. After 4 passes, the first (or last) 4 items are in their final, sorted locations; after 10 passes, the first (or last) 10 items are in their final locations; after all N passes, all N items are in sorted order.

Animation

The Visual Sort section of this page contains small-scale, step-by-step animations of several sorting algorithms. Note that this version of Selection Sort always finds the next largest item and swaps it with the last unsorted item.

• Choose Selection Sort in the first drop-down menu.
• Repeatedly click on Step until you have a sense of how the algorithm works. Then click Run and check whether its continued behavior is what you expect.
• You can click on the New Sort button to get a new set of random data if you want to repeat the process to understand the algorithm better.

Performance

On average, the "finds the next smallest (largest) item" computation in each pass has to look at N/2 still-unsorted items. Since that is done in all N passes, the algorithm takes approximately N * N/2 steps to go from completely unsorted data to sorted data.

Code

Note that this version of Selection Sort, unlike the animation above, always finds the next smallest item and swaps it with the first unsorted item.

    // Selection Sort: Find the minimum item in progressively smaller ranges
    // of the data, moving each minimum item to the beginning of that range.
    void sort(int[] data, int numItems)
    {
        // Each time through the loop, startIndex is the beginning of the
        // next range of data being sorted.
        for ( int startIndex = 0; startIndex < numItems; startIndex++ )
        {
            // Find the minimum item in the range starting at startIndex.
            // Start by assuming the first item is the minimum.
            int minIndexSoFar = startIndex;
            for ( int index = startIndex + 1; index < numItems; index++ )
            {
                // If this item is smaller than the minimum seen so far,
                // this is the new minimum seen so far.
                if ( data[index] < data[minIndexSoFar] )
                {
                    minIndexSoFar = index;
                }
            }

            // Swap the minimum item found with the first item in this range
            swap(data, startIndex, minIndexSoFar);
        }
    }

    // Swap the item at index1 with the item at index2.
    void swap(int[] data, int index1, int index2)
    {
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }