Sort an integer array using selection sort algorithm in java (with example)

What is selection sort algorithm?

• Selection sort is sorting technique used to sort the elements in list data structure like array.
• The selection sort is quite simple algorithm.
• The time complexity of selection sort algorithm is O(n^2).
• The logical flow of selection sort is as follows
  • Given an unsorted integer array.
  • Array will be virtually divided into two halves.
    • Sorted array and unsorted array.
    • Initially sorted array will be empty and unsorted array will be full.
  • We will select or find minimum element from unsorted array and move it to sorted array.
  • After every iteration data starts moving from unsorted array to sorted array.
    • Slowly all the elements will be moved to sorted array.
• We will get sorted array using selection sort algorithm.

Algorithm: sort an integer array using selection sort in java

1. Given an unsorted integer array of length n.
2. We will use two for loop to sort an input array.
3. Start iterating through the array
   • Outer for loop will iterate from 0 to n – 1 and let the index will be outerindex.
   • Select current index are as probable minimum element in unsorted array.
   • Start inner for loop from outerindex  + 1 to n.
     • Find minimum element in an array i.e. right side of outerindex + 1.
     • Add minimum element to sorted list.
4. Once, we are out of loop, we will get the sorted array.

Example- sort integer array using selection sort algorithm in java.

• Let us take an example to understand, the working of selection sort algorithm (step by step).
• Given a input array, which we would like to sort using selection sort

• We divide the array in two parts (Sorted array and unsorted array) [Refer Fig 2]
  • Initially sorted array will be empty and unsorted array will be full.
  • We will select the minimum element from unsorted array.
    • Then, we will put minimum element to sorted array.
  • We assumes 10 as probable smallest element in unsorted array
    • We will iterated unsorted the rest of array to find the smallest element
    • We will find 7 as the smallest element
    • We will swap smallest element with probable smallest element (10) i.e 7 with 10
    • So, we will get first element for our sorted array i.e. 7
  • We will get array as {7, 10, 25, 20, 12, 9} after first iteration

• After first iteration, we will have array {7, 10, 25, 20, 12, 9}, where 7 got its final position.
  • We will select next element i.e. 10 as probable smallest element [Refer Fig: 3]
  • Now, we will the find smallest element in rest of the array (from 2 to 5).
    • Smallest element will be 9.
  • Swap the probable smallest element i.e 10 with actual element 9.
  • We will get array as {7, 9, 25, 20, 12, 10} after second iteration

• After second iteration, we will have array {7, 9, 25, 20, 12, 10} where 7 and 9 got its final position.
  • We will select next element i.e. 25 as probable smallest element [Refer Fig: 4]
  • Now, we will find the smallest element in rest of the array (from 3 to 5).
    • Smallest element will be 10.
  • Swap the probable smallest element i.e 25 with actual element 10.
  • We will get array as {7, 9, 10, 20, 12, 25} after third iteration

• After third iteration, we will have array {7, 9, 10, 20, 12, 25} where 7,9,10 got its final position.
  • Similarly in fourth iteration, we will get output as {7, 9, 10, 12, 20, 25}

• After fourth iteration, we will have array {7, 9, 10, 12, 20, 25} where 7,9,10,12 got its final position.
  • Similarly in fifth iteration, we will get output as {7, 9, 10, 12, 20, 25}
  • 7,9,10,12 and 20 got its final position
  • Element 25 implicitly got its final position.
    • As we have sorted n-1 elements, the nth element will automatically get its final position
  • So, we got the sorted array.

Performance analysis of selection sort algorithm

Program – sort an integer array using selection sort algorithm in java

package org.learn.arrays;

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {
		
		int[] example1 = { 10, 7, 25, 20, 12, 9 };
		System.out.println("Unsorted array is : "+Arrays.toString(example1));
		selectionSort(example1);
		
		int[] example2 = { 5, 4, 3, 2, 1, 0 };
		System.out.println("\nUnsorted array is : "+Arrays.toString(example2));
		selectionSort(example2);
	}

	private static void selectionSort(int[] arr) {
		int length = arr.length;
		for (int outterIndex = 0; outterIndex < length - 1 ; outterIndex++) {
			//mark current index as minimum value index
			int iCurrentMin = outterIndex;
			for (int innerIndex = iCurrentMin + 1;  innerIndex < length; innerIndex++) { if (arr[iCurrentMin] > arr[innerIndex]) {
					//save the actual min value index
					iCurrentMin = innerIndex;
				}
			}
			//If current element is not smallest, let us swap it
			if(iCurrentMin != outterIndex) {
				swap(arr,iCurrentMin, outterIndex);
			}
		}
		System.out.println("Sorted Array is   : "+ Arrays.toString(arr));
	}

	private static void swap(int[] arr, int index_1, int index_2) {
		int temp = arr[index_1];
		arr[index_1] = arr[index_2];
		arr[index_2] = temp;
	}
}

Output – sort an array using selection sort algorithm in java

Unsorted array is : [10, 7, 25, 20, 12, 9]
Sorted Array is   : [7, 9, 10, 12, 20, 25]

Unsorted array is : [5, 4, 3, 2, 1, 0]
Sorted Array is   : [0, 1, 2, 3, 4, 5]