selection sorting algorithm


In my previous article about bubble sort, I have discussed thoroughly bubble sort. if you haven’t checked it yet give it some time over a coffee. 

Why not bubble sort?

Firstly, Assuming that you know the bubble sort, let me briefly say why it is not an effective sorting algorithm. Bubble sorting is not the best sorting algorithm for a majority of two reasons.

  1. Time complexity increases quadratically(O(n^2)) as the input size increases.
  2. Each and every comparison requires a swap if the previous element is greater than the current element.
Swapping operation is time-consuming and memory consuming for every comparison. But If we think of bubble sort a bit thoroughly we can eliminate this swapping for every comparison and swap only once.
 

Introduction to selection sort:-

Firstly, Let’s assume that we have 10 apples. These apples need to be sorted according to the size of each apple in the increasing order. Now using bubble sort, We compare every two apples and swap them if the previous one is bigger than the current one. 
 
Now, what if we remember the position(index) of the smaller apple in a local variable (currentMinimumIndex). Keep updating this variable as we continue the comparison. By doing so, we will have the index of the smallest apple in the variable currentMinimumIndex at the end of the comparison cycle. Now we need to swap the elements at the nth comparison and currentMinimumindex value for one time.

 

The name of the selection sort comes from this process only as we are selecting a minimum value in each comparison cycle.

To understand it better, See the below comparison between bubble sorting and selection sorting.

Bubble sorting
selection sorting
Since we know the logic behind selection sort, let’s convert it into the pseudocode.

Pseudocode for selection sort:-

Pseudocode of the selection sort is as explained below.
  1. Start a loop with variable i from 0 to length of the array.
  2. Consider the element at the ith index of array as is the minimum value of the array. so take i as the currentMinimum index.
  3. Start another loop with a variable j starting from i+1 till the length of the array.
  4. Compare the elements at variable currentMinimumindex and jth position.
  5. if the element at jth index is smaller than currentMinimumIndex, Update the currentMinimumIndex to j.
  6. swap the elements at position i and currentMinimumIndex (if both of them are same no swapping required)
  7. repeat the same process for all elements.
  8.  return the sorted array.
Let’s convert this pseudocode into the code now.
public class SelectionSort {
public static int[] selectionSort(int[] a) {
int lengthOfArray=a.length;
for(int i=0;i<lengthOfArray;i++) {
int currentMinimumIndex=i;
for(int j=i+1;j<lengthOfArray;j++) {
if(a[currentMinimumIndex]>a[j]) {
currentMinimumIndex=j;
}
}
int temp= a[i];
a[i]=a[currentMinimumIndex];
a[currentMinimumIndex]=temp;
}
return a;
}
public static void main(String[] args) {
int[] unsortedArray= {-2,0,100,10,3};
for(int a :selectionSort(unsortedArray)) {
System.out.println(a);
}
}
}

function selectionSort(a) {
var lengthOfArray = a.length;
for (var i =0; i < lengthOfArray; i++) {
var currentMinimumIndex = i;
for (var j = i +1; j < lengthOfArray; j++) {
if (a[currentMinimumIndex] > a[j]) {
currentMinimumIndex = j;
}
}
var temp = a[i];
a[i] = a[currentMinimumIndex];
a[currentMinimumIndex] = temp;
}
return a;
}

Time complexity analysis of selection sort:-

As we discussed in the introduction to the selection sort, The reason why we use selection sort over bubble sort is to skip the swapping operations for every element. Though there is only one swapping operation, There are multiple loops to be executed to find the current minimum or maximum index. So By following the rules of big o notation, the simplified time complexity of the selection sort comes down to O(n2).
 

Space complexity of the selection sort:-

By Observing the above code we can say that selection sorting algorithm is an in-place sorting algorithm as the unsorted array itself converted to sorted array in the same variable. But we added a couple of local variables to keep track of the indexes of current minimum value and length of the array. These variables take a constant amount of space in the memory. So we can generalize the space complexity of the selection sort as O(1).