Selection Sort

17 July 2009, 06:07 PM

*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. */`

publicvoidselectionSort(int[] data) {intmin, v ;for(inti=0;i<data.length;i++) { min = i ;for(intj=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 ; } }

Last edited on 17 July 2009

### Comments

Post a comment~

nette, 19 August 2010, 12:23 PM