Explaining Selection Sort Algorithm in Simple English

In this Blog, we will discuss the Selection Sort Algorithm and its working procedure. Selection sort is an in-place comparison-based sorting algorithm that sorts the array by repeatedly finding and swapping the minimum element with the leftmost element of the array. 

In-place means that the algorithm does not use extra space for manipulating the input but may require a small though non-constant extra space for its operation. Usually, this space is O(log n), though sometimes anything in O(n) (Smaller than linear) is allowed.

In this algorithm, the array is divided into two parts. One part will initially be empty but will contain the sorted array and is placed on the left-hand side, while the other part carries the original unsorted array and is placed on the right-hand side. In every iteration, the minimum element is picked from the unsorted list and gets placed at the beginning of the sorted array, thus reducing the size of the unsorted array by one while at the same time increasing the size of the sorted array by 1.

Now that we have understood what selection sort is, let’s understand its working procedure with a simple example of an array with a length of 5.

How Selection Sort Algorithm Works

The working principle of this algorithm is very simple. As told, we just have to find the minimum element from the unsorted array and place it at the beginning of the sorted array. 

To begin with we have to assume that the first element of the unsorted subarray is the minimum element of the array. Then by iterating and comparing every element of this unsorted array with the first element which we have assumed to be the minimum element of the array we have to find the minimum element of the array.

If we find any element less than our current min element, that element becomes the new min of the array and the journey continues till the last element. Upon reaching the end of the array, simply replace the leftmost element of the unsorted array with the current min element. We have to do this every time until the array is sorted completely.

Let’s take an example of an array of length 5 to understand it better

Since the array we are using is of length 5, we will be making 4 passes. One pass per element,  and as for the last element, it will be automatically sorted. Thus we can say that for an array of size n, n-1 passes are required to sort that array using selection sort

First Pass

In this, we have our array in the unsorted part. Here we will assume that the first element of the array is the min element, and start comparing it with the rest of the array elements to find an element smaller than it.

After the first traversal, we found that 0 is less than 8, thus updating our min from 8 to 0. On the further traversal, we found that 0 is less than 7, 1, and 3. This makes 0 the final min value of this pass.

As we have reached the end of the array, we will conclude our first pass by simply swapping our min value (which in this case is 0) with the leftmost value of the unsorted array (which is 8), and we have our first element of the sorted array

Second Pass

As always we will start with the left-most element of the unsorted array or the first element of the unsorted array whose size has now been reduced to 4. Hence the number of comparisons would be 3. 

We will follow the same procedure as we did in the first pass, assuming the first element as our min element and now the comparison starts by iterating over each element of the array.

After the first traversal, we found that 7 is less than 8, thus updating our min from 8 to 7. On the second traversal, we found that 1 is less than 7, thus updating our min value again. And on the last traversal as 3 is greater than 1, hence we will not be updating min..

As we have reached the end of the array, we will conclude our second pass by simply swapping our min value (which in this case is 1) with the leftmost value of the unsorted array (which again is 8), and we get our second element of the sorted array

The process will remain the same for both the third and the fourth pass as it was for the first two passes.

After all the passes are done, our sorted array will look like

Algorithm

1. Initialize a variable – min
2. Iterate the unsorted array from the 0^th index to n-1.
3. Set this min variable equal to i. This will make sure that our min variable always starts from the first element.
4. Start another loop j from i+1 till the end of the array for comparing the min element with the rest of the elements of the array to find the smallest element in the array.
5. If reached the end of the array, simply swap the left-most element with the current min element.
6. Repeat this process until the array is sorted.

Pseudo Code

package com.Tekolio.Sort;
import java.util.*;
class Main {
    public static void main(String[] args) {
        int[] A = {8, 0, 7, 1, 3};
        System.out.print(Arrays.toString(solve(A)));
    }
    public static int[] solve(int[] A) {
        //initializing min variable
        int min = 0;
        for(int i=0; i<A.length; i++) {
            min = i;
            //comparing value at min with the rest of the Arrays
            //changing min if any value is smaller than at min
            for(int j=i+1; j<A.length; j++) {
                if(A[min] > A[j]) {
                    min = j;
                }
            }
            //swappinh min with the first element of the array
            int temp = A[i];
            A[i] = A[min];
            A[min] = temp;
        }
        return A;
    }
}

#include <bits/stdc++.h>
using namespace std;
//Swapping Function
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
void selectionSort(int A[], int n)
{
    int i, j, min;
 
    // One by one move boundary of
    // unsorted subarray
    for (i = 0; i < n-1; i++)
    {
       
        // Find the minimum element in
        // unsorted array
        min = i;
        for (j = i+1; j < n; j++)
        if (A[j] < A[min])
            min = j;
 
        // Swap the found minimum element
        // with the first element
        swap(&A[min], &A[i]);
    }
}
 
//Function to print an array
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout << A[i] << " ";
    cout << endl;
}

int main()
{
    int A[] = {8, 0, 7, 1, 3};
    int n = sizeof(A)/sizeof(A[0]);
    selectionSort(A, n);
    printArray(A, n);
    return 0;
}

import sys
A = [8, 0, 7, 1, 3];
 
# Traverse through all array elements
for i in range(len(A)):
     
    # Find the minimum element in remaining
    # unsorted array
    min = i
    for j in range(i+1, len(A)):
        if A[min] > A[j]:
            min = j
             
    # Swap the found minimum element with
    # the first element       
    A[i], A[min] = A[min], A[i]
 
# Driver code to test above
for i in range(len(A)):
    print("%d" %A[i],end=" ")

Time Complexity – O(n²)

This is because there are two nested loops – one loop is used to select the elements of the array one by one, while the other is used to compare that element with every other element of the array

• Worst Case Complexity: O(n²)

The worst occurs when an array in descending order has to be sorted in ascending order.

• Best Case Complexity: O(n²)

It occurs when the array is already sorted

If the array is already sorted then also the time complexity is O(n²), this is because in selecting sort the algorithm will check for the smallest element in the array on every iteration regardless of the placement of the elements.

• Average Case Complexity: O(n²)

It occurs when the elements of the array are. in jumbled order (neither ascending nor descending).

Auxiliary Space: O(1) 

This is because this technique is an in-place sitting technique where the only space used is for the temporary variable used for swapping two values in the array

The good thing about selection sort is that it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Points to Remember

1. Selection sort is not a stable sorting technique. This is because it fails in maintaining the original order of elements.
2. It is not a recursive technique.
3. It is not an adaptive technique as well. This is because it will check for the smallest element by assuming the first element as the smallest even if it’s the smallest among all the elements of the array.

Where to use Selection Sort

1. Where there is a small array of elements that need to be sorted
2. Where the cost of the swapping does not matter
3. Where checking all the elements is compulsory

Frequently Asked Questions