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
- Given an unsorted integer array of length n.
- We will use two for loop to sort an input array.
- 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.
- 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
| S. No. | Cases | Complexity |
|---|---|---|
| 1 | Best case | O(n^2) |
| 2 | Average case | O(n^2) |
| 3 | Worst case | O(n^2) |
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] |