Tech-Algorithm.com

Selection sort is probably the easiest sort to remember and implement - arguably even simpler than bubble sort. It works as follow, first find the smallest element and swap it with the first (left-most) element. If the smallest element is the first element itself then nothing happens. Secondly find the smallest element starting from the second element and swap it with the second element if necessary. Do the same for third, fourth, and so on until you reach the last right-most element which should be automatically be the biggest element. Sounds complicated? Don't worry, if this is difficult to imagine you can check on the following applet to see it in action for yourself.


Applet: Selection sort demo applet. Click it to reset with new elements.

Here is a tip before reading further: Observe the applet especially the yellow bar. Do this a few time if necessary.

Now some explanation for the applet if you haven't figured it already. There are three things of interest in the applet. A red and a blue vertical line, and one yellow bar. The red line starts from the left and moves slowly towards the right. The blue line moves fast and always start from the red line, selecting the smallest element along the way. The smallest element is indicated by the yellow bar. Once the blue line reaches the right end, the yellow bar is then swapped with the element currently on the red line. The red line move one step to the right and the blue line resets back to find the next smallest element. This continues until the red line reaches the right end.

You'll notice obvious separation between the left and the right side of the red line. To the left all elements are sorted and to the right not yet. The not so obvious thing is, selection sort does very little element swapping, unlike other algorithm where swaps happens quite a lot. In comparison, bubble and selection sort is about the same, except bubble sort does much much more work (swaps). On the other hand, the only good thing about selection sort is probably the amount of swaps it does. This is critical if swapping element is an expensive process! Unfortunately for selection sort, there is actually a way for any sorting algorithm to use the same little amount of swaps by having the algorithm operate indirectly on the elements. This can be achieved with an indices array - but I'm straying.

This silly jibba jabba bores you to no end? That's understandable. I too am often eager for the meat myself, and as you wish, the following is a Java implementation for selection sort. Look at it and then shrug it off your mind (just like how you did it with bubble). This isn't something you'd want lurking anywhere within your legacy application - especially when Mr. Perfectionist is going to do code review.

/**
 * SelectionSort data. Sorting is in-place.
 * @param data Array to sort.
 */    
public void selectionSort(int[] data) {
    int min, v ;
    for (int i=0;i<data.length;i++) {
        min = i ;
        for (int j=i+1;j<data.length;j++) {
            // find the smallest element index
            if (data[j] < data[min]) min = j ;
        }
        // now swap the smallest element
        v = data[i] ;
        data[i] = data[min] ;
        data[min] = v ;
    }
}