Selection Sort is yet another fairly simple sorting algorithm. It is more efficient than BubbleSort. Selection Sort works like this:

• There are two parts in the array:
  • Unsorted zone
  • Sorted zone
• In a loop, the highest element from the unsorted zone is selected (hence the name Selection Sort) and placed at the end of the unsorted zone. After that, the sorted zone expands to cover the recently moved element, and the unsorted zone shrinks to lose that element. Eventually, the sorted zone becomes the entire array, and the unsorted zone disappears. The array is then considered to be sorted.

One possible way to code the Selection Sort algorithm in Java is as follows:

public int[] selectionSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
	for(int i = array.length - 1; i >= 0; i--)		// start at the end of the array
	{
		int highestIndex = i;				// (1) default value of the highest element index.
		for(int j = i; j >= 0; j--)			// (2) loop from the end of unsorted zone to the
								//  beginning of the array.
		{
			if(array[j] > array[highestIndex])	// compare current element to highest
				highestIndex = j;		// if it's higher, it becomes the new highest
		}
		// swap the two values
		int temp = array[i];
		array[i] = array[highestIndex];
		array[highestIndex] = temp;
	}
	return array;
}

(1) Default value of the highest element index will be the first element we're checking, since we've only checked one element.

(2) Loop from the end of unsorted zone to the beginning of the array. You may prefer to do it the other way around, that is from the beginning to the end of the unsorted zone, which is right up until the start of the sorted zone. If you do that, make sure to set initial highest index to 0 instead of i.

These are the steps taken to sort the array using BubbleSort:

Elements in blue indicate comparisons.
Elements in red indicate swaps.
The text in green indicates comments.
Light gray highlighting indicates the unsorted zone of the array.
Dark gray highlighting indicates the sorted zone of the array.

[3][5][4][9][2] -- original
2 is the initial highest element
[3][5][4][9][2] -- compare 2 to 2 (pointless)
[3][5][4][9][2] -- compare 2 to 9
9 is the new highest element
[3][5][4][9][2] -- compare 9 to 4
[3][5][4][9][2] -- compare 9 to 5
[3][5][4][9][2] -- compare 9 to 3
[3][5][4][2][9] -- swap 2 and 9
2 is the initial highest element
[3][5][4][2][9] -- compare 2 to 2 (pointless)
[3][5][4][2][9] -- compare 2 to 4
4 is the new highest element
[3][5][4][2][9] -- compare 4 to 5
5 is the new highest element
[3][5][4][2][9] -- compare 5 to 3
[3][2][4][5][9] -- swap 2 and 5
4 is the initial highest element
[3][2][4][5][9] -- compare 4 to 4 (pointless)
[3][2][4][5][9] -- compare 4 to 2
[3][2][4][5][9] -- compare 4 to 3
[3][2][4][5][9] -- swap 4 and 4 (pointless)
2 is the initial highest element
[3][2][4][5][9] -- compare 2 to 2 (pointless)
[3][2][4][5][9] -- compare 2 to 3
3 is the new highest element
[2][3][4][5][9] -- swap 2 and 3
2 is the initial highest element
[2][3][4][5][9] -- compare 2 to 2 (pointless)
[2][3][4][5][9] -- swap 2 and 2 (pointless)
[2][3][4][5][9] -- we are done!
			

As you may have noticed, my implementation of Selection Sort does some comparisons and swaps which are completely pointless. For selection sort, in general, it's simpler as well as more efficient to do a couple of pointless comparisons/swaps than to check every single operation for pointlessness, especially on large arrays of data. For the demonstration purposes, I have modified my code to point out all pointless comparisons and swaps in case you're as curious as I am.

I hope that my article has helped you get a better understanding of how Selection Sort works. Good luck!

Written by Pavel Bennett.