Selection Sorting in Java Program with Example

How does Selection Sort work?

Selection Sort implements a simple sorting algorithm as follows:

• Algorithm repeatedly searches for the lowest element.
• Swap current element with an element having the lowest value
• With every iteration/pass of selection sort, elements are swapped.

Every pass therefore treats the array as two regions: a sorted block that grows from the left and an unsorted block that shrinks on the right. The algorithm walks the unsorted block, remembers the index of the smallest value it meets, and exchanges that value with the first unsorted position.

Because only one exchange happens per pass, an array of n elements is ordered after at most n-1 swaps. That property is what separates this routine from the other beginner-level Java sorting algorithms, which move data far more often.

The trace below follows the sample array {860, 8, 200, 9} exactly as the program in the next section prints it at run time.

Two details in that trace are worth pausing on. First, pass 3 still reports a swap even though the order does not change, because the smallest remaining value already sits at the current index and the program exchanges the element with itself. Second, the number of comparisons falls by one on each pass (three, then two, then one), which is the pattern behind the complexity figures further down the page.

Java Program to implement Selection Sort

The class below is named SelectionSortAlgo and sits in the package com.guru99. The main() method declares the sample array, prints it, hands it to selection() for sorting, and prints it again. The helper printArray() writes all elements on a single line, which is what produces the readable pass-by-pass log.

Inside selection(), the outer loop marks the boundary between the sorted and unsorted regions, the variable index holds the position of the smallest value seen so far, and the three assignments at the end of each pass perform the swap.

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

Output:

Compiling and running the class produces the console log below, with one block of output per pass.

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

Two problems catch beginners out when they run this example for the first time. Because the file declares package com.guru99;, the source must live in a matching com/guru99 directory, otherwise the compiler reports a package or class-name mismatch. The class must then be launched by its fully qualified name, java com.guru99.SelectionSortAlgo, because plain java SelectionSortAlgo raises NoClassDefFoundError.

The loop bounds are the other common trap. The outer loop stops at array.length - 1 and the inner loop starts at i + 1; changing either boundary produces an extra empty pass or an ArrayIndexOutOfBoundsException.

Time and Space Complexity of Selection Sort

The inner loop in the program always runs to the end of the array, so the algorithm performs the same number of comparisons whatever the data looks like. For an array of n elements that total is n(n-1)/2, which for the four-element sample equals six, and the output above indeed prints exactly six Comparing lines.

Three consequences follow from that uniform row of figures:

• Selection sort is not adaptive. Sorted input costs precisely as much as reversed input, so there is no early-exit shortcut of the kind bubble sort offers.
• The swap count is the algorithm’s strong point. At most n-1 exchanges take place, which is far fewer than the quadratic number of moves other simple sorts can make.
• Memory use is constant. Only the loop counters and the two temporary variables index and smallerNumber are needed, so auxiliary space is O(1) and the sort happens in place.

The quadratic growth is the practical limit. Doubling the array size roughly quadruples the comparison work, so selection sort suits teaching, small arrays, and embedded code rather than production data sets, where O(n log n) algorithms are the correct choice.

Advantages and Disadvantages of Selection Sort

Understanding where the algorithm helps and where it hurts makes it easier to decide when reaching for it is reasonable.

Advantages

• The logic is short and readable, which is why it is a standard first sorting exercise alongside insertion sort.
• It sorts in place, so no second array is allocated and memory use does not grow with the input.
• It performs at most n-1 writes to the array, which matters on storage where writes are slow or wear out the medium.
• Its running time is completely predictable, because the comparison count depends only on the array length.

Disadvantages

• Every case is O(n²), so the algorithm does not scale to large collections.
• It cannot detect an already sorted array and therefore never finishes early.
• The classic form shown above is unstable, so two equal values may end up in the opposite order.
• It compares more often than insertion sort on nearly ordered data, where insertion sort approaches linear time.

In short, choose selection sort when the array is small and each write is expensive, and avoid it whenever the data set is large or already close to sorted.

Selection Sort vs Bubble Sort vs Insertion Sort

All three algorithms are quadratic, in-place comparison sorts, yet they behave differently once the shape of the input changes.

The table explains a common interview answer. Selection sort wins on the number of exchanges, bubble sort wins on recognising input that is already ordered, and insertion sort is usually the fastest of the three in practice because real data is often partly sorted. None of them competes with merge sort or quicksort once the array grows past a few dozen elements.

FAQs