A Simple Selection Sort

I've seen many example in the web which make you to follow a lot of indices and nested loops which makes selection sort look difficult. The intent here is to help you understand the concept and code in few minutes.

Find the index of minimum in an array
The key to understand selection sort is first to write a simple function that would find the minimum value in an array and return its index. Here is a simple code to do it.

/*
 * Finds the smallest element in the array
 *
 * Eg : If 4th element in the array is smallest 
 * it return 3, since array index starts from 0.
 *
 * @ returns the index of the smallest element 
*/
public int findSmallestElement(int array[]) {
 
 int minIndex = 0;
 int value = array[0];
 
 for (int i = 0; i < array.length ; i++) {
            if (value > array[i]) {
                minIndex =  i;
                value = array[minIndex];
            }
        }

        return minIndex;
}

Find the index of smallest element from a given index
Now we'll tweak the above code to return the index of minimum element from a given index, Its something like find the smallest element in the array starting from index 3 i.e smallest element in the sub array starting from index 3 to the end of array.

The implementation is simple, The modified function now takes a additional parameter called startIndex from which it look for the smallest element in the rest of the array
( previously we assumed the starting index as 0, now we have a parameter in the method which defines this - Just compare the below code with above sample code )

/*
     * Finds the smallest element from the given startIndex
     *
     * @ returns the index of the smallest element.
     */
    private int findNextSmallestElement(int startIndex, int array[]) {

        int minIndex = startIndex;

        int value = array[startIndex];

        for (int i = startIndex ; i < array.length; i++) {
            if (value > array[i]) {
                minIndex = i;
                value = array[minIndex];
            }
        }

        return minIndex;
    }

Now we have this method, lets look at selection sort algorithm itself.

Selection Sort algorithm
(Here is what Wikipedia says about the algorithm)
The selection sort algorithm works as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.

Code
Now lets try to code this algorithm in the simplest possible way as explained above.

public void selectionSort(int array[]) {

        //Start from first element
        for (int index = 0; index < array.length; index++) {

            //find the next smallest element
            int minIndex = findNextSmallestElement(index, array);

            // Swap code
            int temp = array[minIndex];
            array[minIndex] = array[index];
            array[index] = temp;
        }
    }

Done, that's it. As you can see the algorithm can be implemented in few lines, easy to remember once you get the basics.

We have already coded the findNextSmallestElement() method. It is simple as finding a smallest element in the array (starting from a given index)

What is the complexity of the above algorithm ?
 Its O(n²) - Since there is a nested loop.

There is loop in the selectionSort() method which calls findNextSmallestElement() which again has a loop hence nested loop.

Check the other article on How to find the complexity of a code.

Source code
Here is the complete selection sort sample java file used in this post.