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
Fig 1 : Given unsorted array - 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
Fig 2: Array after first iteration of selection sort i.e. 7 at its final position - 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
Fig 3: Array after second iteration of selection sort i.e. 9 at its final position - 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
Fig 4: Array after third iteration of selection sort i.e. 10 at its final position - 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}
Fig 5: Array after fourth iteration of selection sort i.e. 12 at its final position - 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.
Fig 6: Array after fifth iteration of selection sort i.e. 25 at its final position 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]
