In this tutorial, we are going to learn about selection sort in detail and its algorithmic implementation.

Selection Sort

• In-place algorithm.
• O(n^2) time complexity - Quadratic.
• It will take 100 steps to sort 10 items, 10000 steps to sort 100 items and 1000000 steps to sort 1000 items.
• Doesn’t require much swapping as bubble sort.
• Unstable algorithm.

Selection Sort Algorithm

Selection_Sort (A, n)

1. Set j = 0.
2. Repeat Step 2 to 4 While j < n – 1:
3. Set Min = j and i = j+1.
4. Repeat step 5 while i < n:
5. if(a[i] < a[Min]), then: Min = i. [End of step 4 loop.]
6. if (Min != j), then:
7. swap (a[j], a[Min]). [End of step 2 loop.]
8. End

Selection Sort Programmatic Implementation in Java

public class SelectionSort {
	public static void main(String[] args) {
		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
		for (int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0; lastUnsortedIndex--) {
			int largest = 0;
			for (int i = 1; i <= lastUnsortedIndex; i++) {
				if (intArray[i] > intArray[largest]) {
					largest = i;
				}}
			swap(intArray, largest, lastUnsortedIndex);
		}
		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}}
	public static void swap(int[] array, int i, int j) {
		if (i == j) {
			return;
		}
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}}

Output:

-22 -15 1 7 20 35 55