Selection sort algorithm

Selection Sort is one of the simplest sorting algorithm, where array is traversed from first element to last element to repeatedly find the minimum element. In this way the array is divided into two sub-arrays sorted and unsorted, in each pass one element is added to sorted array from unsorted array.

It is much less efficient on large data sets than more advanced algorithms such as quicksort, heapsort, or merge sort. Selection sort is an in-place and non-stable sorting algorithm that takes constant O(1) auxiliary space.

Selection sort always takes О(n2)time because of two nested loops.

Selection sort implementation in Java

Lets assume we have an array having (7, 2, 1, 6, 2, 5, 3, 4) integer elements, we will starts a loop from first element (i=0) to end of array (i=n).

An inner loop will traverse through unsorted array to check for minimum element, this element will be placed to start of unsorted part i.e. end of sorted part of array.

2, 7, 1, 6, 2, 5, 3, 4, i=0, j=1
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=2
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=3
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=4
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=5
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=6
1, 7, 2, 6, 2, 5, 3, 4, i=0, j=7
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=2
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=3
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=4
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=5
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=6
1, 2, 7, 6, 2, 5, 3, 4, i=1, j=7
1, 2, 6, 7, 2, 5, 3, 4, i=2, j=3
1, 2, 2, 7, 6, 5, 3, 4, i=2, j=4
1, 2, 2, 7, 6, 5, 3, 4, i=2, j=5
1, 2, 2, 7, 6, 5, 3, 4, i=2, j=6
1, 2, 2, 7, 6, 5, 3, 4, i=2, j=7
1, 2, 2, 6, 7, 5, 3, 4, i=3, j=4
1, 2, 2, 5, 7, 6, 3, 4, i=3, j=5
1, 2, 2, 3, 7, 6, 5, 4, i=3, j=6
1, 2, 2, 3, 7, 6, 5, 4, i=3, j=7
1, 2, 2, 3, 6, 7, 5, 4, i=4, j=5
1, 2, 2, 3, 5, 7, 6, 4, i=4, j=6
1, 2, 2, 3, 4, 7, 6, 5, i=4, j=7
1, 2, 2, 3, 4, 6, 7, 5, i=5, j=6
1, 2, 2, 3, 4, 5, 7, 6, i=5, j=7
1, 2, 2, 3, 4, 5, 6, 7, i=6, j=7

package com.tb.arrays.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class SelectionSort {
	static int[] input = { 7, 2, 1, 6, 2, 5, 3, 4 };

	private static void sort(int[] input, int n) {

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (input[j] < input[i]) {
					int tmp = input[j];
					input[j] = input[i];
					input[i] = tmp;
				}
			}
		}
	}

	private static String printArrays(int[] input) {
		return Arrays.stream(input).mapToObj(String::valueOf).collect(Collectors.joining(", "));

	}

	public static void main(String[] args) {
		System.out.println("Array before sort: " + printArrays(input));
		sort(input, input.length);
		System.out.println("Array after sort: " + printArrays(input));
	}
}
Output: Output of above code will be something like this.

Array before sort: 7, 2, 1, 6, 2, 5, 3, 4
Array after sort: 1, 2, 2, 3, 4, 5, 6, 7
In this article we have seen "What is Selection sort?", Selection sort time complexity, usage and how to implement Selection sort in Java.