Selection Sort in Java
Introduction
This tutorial explains the Selection Sort Algorithm with an example list of 5 numbers.It then provides the Java implementation of Selection Sort Algorithm and explains its Big Oh complexity. The tutorial also contains video explanation of the algorithm and walkthrough of the Java code as well.
What is Selection Sort Selection sort is an in-place sorting algorithm which builds up a sorted sub-list in the same item list by picking up the smallest element from among the unsorted items in the list and placing it at the end of the sorted sub-list. Thus, over multiple iterations the smallest items keep getting picked up from the unsorted sub-list which keeps reducing and are added to the end of the unsorted sub-list which keeps getting larger.
To achieve in-place sorting, i.e. not using any extra space, the algorithm places the smallest item from the unsorted sublist at the tail of the sorted sub-list by swapping the element which is at the tail of the sorted sub-list with the smallest item in the unsorted sub-list.
YouTube video showing whiteboard animation video explanation of how selection sort works and Java code walk-through
Selection Sort Working Explained Lets understand the working of Selection Sort using an example. Lets say the list to be sorted is [10, 5, 100, 1, 10000].
First Pass of Selection Sort
The smallest item in the list is 1. The sorted sub-list will be created in-place at the left of the list. 1 will be swapped with 10. The first pass ends with 1 being placed in its correct position. List has now become [1, 5, 100, 10, 10000] which actually comprises of 2 parts - a sorted sub-list [1] and an unsorted sub-list [5, 100, 10, 10000].
Second pass
The smallest element in the unsorted sub-list is 5. 5 needs to be added to the tail of the sorted sub-list which in an in-place sorting scenario is the head of the unsorted sub-list. I.e. 5 is already in the correct position. The second pass ends with the second element,5, determining its correct sorted position. List has now become [1, 5, 100, 10, 10000] which is composed of a sorted sub-list [1, 5] and an unsorted sub-list [100, 10, 10000].
Further passes
In this way progressively the smallest items from the unsorted sub-list are picked and added to the sorted sub-list by means of swapping with the element immediately preceding the sorted sub-list and the whole list gets sorted in exactly n-1 passes.
OUTPUT of the above code
Explanation of the code
Big Oh Complexity of Selection Sort Algorithm
There are 2 nested loops in the algorithm. The outer loop is for iterations and the inner nested loop is for finding the minimum element from among the unsorted elements. Since the inner loop is nested inside outer loop, the complexity of both the loops together will be O(n2). The complexity of selection sort algorithm is thus O(n2).
(Note - This is a simplified explanation of selection sort complexity. I will be comparing the time complexities of sorting algorithms in a separate article where I will provide detailed mathematical reasoning for the same.)
What is Selection Sort Selection sort is an in-place sorting algorithm which builds up a sorted sub-list in the same item list by picking up the smallest element from among the unsorted items in the list and placing it at the end of the sorted sub-list. Thus, over multiple iterations the smallest items keep getting picked up from the unsorted sub-list which keeps reducing and are added to the end of the unsorted sub-list which keeps getting larger.
To achieve in-place sorting, i.e. not using any extra space, the algorithm places the smallest item from the unsorted sublist at the tail of the sorted sub-list by swapping the element which is at the tail of the sorted sub-list with the smallest item in the unsorted sub-list.
YouTube video showing whiteboard animation video explanation of how selection sort works and Java code walk-through
Selection Sort Working Explained Lets understand the working of Selection Sort using an example. Lets say the list to be sorted is [10, 5, 100, 1, 10000].
The smallest item in the list is 1. The sorted sub-list will be created in-place at the left of the list. 1 will be swapped with 10. The first pass ends with 1 being placed in its correct position. List has now become [1, 5, 100, 10, 10000] which actually comprises of 2 parts - a sorted sub-list [1] and an unsorted sub-list [5, 100, 10, 10000].
Second pass
The smallest element in the unsorted sub-list is 5. 5 needs to be added to the tail of the sorted sub-list which in an in-place sorting scenario is the head of the unsorted sub-list. I.e. 5 is already in the correct position. The second pass ends with the second element,5, determining its correct sorted position. List has now become [1, 5, 100, 10, 10000] which is composed of a sorted sub-list [1, 5] and an unsorted sub-list [100, 10, 10000].
Further passes
In this way progressively the smallest items from the unsorted sub-list are picked and added to the sorted sub-list by means of swapping with the element immediately preceding the sorted sub-list and the whole list gets sorted in exactly n-1 passes.
Selection Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class SelectionSort{
static int intArray[] = { 10, 5, 100, 1, 10000 };
public static void doSort() {
for (int outer = 0; outer < intArray.length; outer++) {
int minPosition=outer;
for(int inner=outer;inner < intArray.length;inner++){
if(intArray[inner] < intArray[minPosition]){
minPosition=inner;
}
}
int temp=intArray[minPosition];
intArray[minPosition]=intArray[outer];
intArray[outer]=temp;
}
}
public static void printArray() {
for (int i = 0; i < intArray.length; i++) {
System.out.print(" " + intArray[i]);
}
}
public static void main(String args[]) {
System.out.print("Array Before Sorting ->");
printArray();
doSort();
System.out.print("\nArray After Sorting ->");
printArray();
}
}Array Before Sorting -> 10 5 100 1 10000 Array After Sorting -> 1 5 10 100 10000
- The
doSort()method in the above java program holds the sorting logic. - There are 2 loops. The loop with the counter
outerrepresents the passes and continues for0tototal-item-count - 1times. ie. 1 less than the number of items times. - The loop with the counter
innerrepresents the search for the smallest item in the unsorted sub-list which starts from the top of the unsorted sublist index i.e the current value ofouterand ends at the end of the list. - The
main()method orchestrates the sorting. - The instance element
intArray[]holds the list to be sorted.
(Note - This is a simplified explanation of selection sort complexity. I will be comparing the time complexities of sorting algorithms in a separate article where I will provide detailed mathematical reasoning for the same.)