Selection Sort in Java and Complexity Analysis

Selection sort is a sorting algorithm, precisely an in-place comparison sort. The selection sort improves over the bubble sort by reducing the number of swapping necessary from O(n²) to O(n). But the number of comparisons remains O(n²).

Selection Sort Java Example

package com.sneppets.dsalgo;

public class SelectionSortExample {
	
	public static int[] doSelectionSort(int[] inArray){
		
		int i, j, nElements, min;
		
		nElements = inArray.length;
		
		for(i=0; i < nElements-1; i++)	//outer loop
		{ 			
			min = i;		//minimum
			
			for (j = i+1; j < nElements; j++) //inner loop
			{
				//if min is greater, we have a new min
				if(inArray[j] < inArray[min]){ 
					min = j;
				}
			} 
			//At the end of inner loop min points to the minimum value
			//and the array elements pointed to by i and min are swapped.
			
			//swap
			swap(i, min, inArray);			
		}
		
		return inArray;
	}

	private static void swap(int i, int min, int[] inArray) {
		
		int temp = inArray[min];
		inArray[min] = inArray[i];
		inArray[i] = temp;	
	}
	
	public static void main(String[] args){
		
		int[] inArray = {24,10,2,30,15,6,20,8};

		System.out.println("Array elements before selection sort");
		printArrayElements(inArray);

		System.out.println("Array elements after selection sort");
		int[] outArray = doSelectionSort(inArray);
		printArrayElements(outArray);
	}

	private static void printArrayElements(int[] inArray) {
		for(int i=0; i<inArray.length; i++){
			System.out.print(inArray[i] + ", ");
		}
		System.out.println("\n");		
	}

}

Output

Array elements before selection sort
24, 10, 2, 30, 15, 6, 20, 8, 

Array elements after selection sort
2, 6, 8, 10, 15, 20, 24, 30,

Note: At each new position of j, the elements inArray[j] and inArray[min] are compared. At the end of the inner loop, min points to the minimum value and the array elements pointed to by j and min are swapped.

Time Complexity

The selection sort performs the same number of comparisons as the bubble sort, which is n*(n-1)/2. However the number of swaps required is fewer when compared to bubble sort. But for larger values of n, the comparison time will dominate compared to swap time, so we should say that selection sort runs in O(n²) time like bubble sort.

Space Complexity

The space for section sort is O(1), because the above algorithm requires only a single additional memory space for temp variable.

Recommended Posts

• Bubble Sort and Complexity Analysis
• Running time in Big O notation for Arrays Algorithms
• How to calculate binary Search time and space complexity

References:

1. Different kinds of sorting
2. Wikipedia sorting algorithm