selection sort

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(n2) to O(n). But the number of comparisons remains O(n2).

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(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");

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

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

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(n2) 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


  1. Different kinds of sorting
  2. Wikipedia sorting algorithm
Inline Feedbacks
View all comments