Selection Sort Java Example

Selection Sort is a simple and slow sorting algorithm that repeatedly selects the lowest or highest element from the un-sorted section and moves it to the end of the sorted section. Mostly, performance wise, it is slower than even Insertion Sort. It does not adapt to the data in any way so its runtime is always quadratic.

But you should not conclude that selection sort should never be used. Good thing is that selection sort has the property of minimizing the number of swaps with each iteration. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

Selection Sort Algorithm

Below is logical code structure or pseudo code of selection sort in general.

for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
//-> invariant: a[k] smallest of a[i..n]
swap a[i,k]
//-> invariant: a[1..i] in final position
end

In plain English, following things happen:

1. Data elements are grouped into two sections: a sorted section (initially empty) and an un-sorted section (initially complete array).
2. Assuming the sorting order is from low to high, find the element with the lowest comparable order from the un-sorted section.
3. Place the found element to the end of the sorted section.
4. Repeat step 2 and 3 until no more elements left in the un-sorted section.

Selection Sort Java Sourcecode

Below is a sample selection sort implementation in java.

public class SelectionSortExample 
{
	public static void main(String[] args) {
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

		// Let's sort using selection sort
		selectionSort(array, 0, array.length);

		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void selectionSort(Object[] array, int fromIndex, int toIndex) 
	{
		Object d;
		for (int currentIndex = fromIndex; currentIndex < toIndex; currentIndex++) 
		{
			int indexToMove = currentIndex;
			for (int tempIndexInLoop = currentIndex + 1; tempIndexInLoop < toIndex; tempIndexInLoop++) 
			{
				if (((Comparable) array[indexToMove]).compareTo(array[tempIndexInLoop]) > 0) 
				{
					//Swapping
					indexToMove = tempIndexInLoop;
				}
			}
			d = array[currentIndex];
			array[currentIndex] = array[indexToMove];
			array[indexToMove] = d;
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

If you guys know any way to improve the performance of selection sort, then please share. I am clueless.

Happy Learning !!