SELECTION SORT ALGORITHM

INTRODUCTION

In this tutorial, we are going to learn about the selection sort algorithm. It is a simple and efficient algorithm which is widely used for sorting elements. In the selection sort, the name itself suggests that we select the specific element on the basis of the condition.  The implementation of the selection sort algorithm is as so simple that it is done by repeatedly selecting the smallest element from the unsorted portion of the array and then swapping it into the sorted portion. This procedure is continuously done till we obtain the sorted set of elements.

The implementation of the selection sort algorithm mainly follows two portions.

1. Sorted portion

2. unsorted portion

In each iteration of the selection sort, the smallest element in the unsorted array is moved to the first position of the unsorted array and this smallest element is considered as the sorted portion of the array.

Arr= [23 ,56 ,32 ,78 ,12]

In the first pass, the first position of the array is considered as the sorted portion and the whole array is traversed from starting. After traversing the array, we have got 12 as the smallest element. So, swap 11 with 23.

Swapping of the elements is taken place like this.

23 56 32 78 12
12 56 32 78 23

Now, 12 is actually the only element in the sorted portion. Now, we traverse the whole array leaving 12. In the second pass, 23 is the smallest element and it is replaced with 56.

12 56 32 78 23
12 23 32 78 56

In the third pass, 32is the smallest element and it remains there itself as there is no smaller element in the unsorted portion.

12 23 32 78 56
12 23 32 78 56

In the fourth pass, 56is the smallest element and it is replaced with the 78.

12 23 32 78 56
12 23 32 56 78

In the fifth and the last pass, the largest element in the list automatically gets placed in the last position. Therefore, the resulting array is the sorted array.

The sorted array is 12 23 32 56 78

this is the working of the selection sort algorithm. Now, let’s look at the algorithm for the selection sort.

ALGORITHM

Step 1: Start.
Step 2: Select the smallest element of the unsorted portion and place it in the sorted position.
Step 3: Continue the same process until the penultimate position of the list of elements.
Step 4: Stop.

Let’s look at the code implementing the bubble sort algorithm.

C++ Code:

#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[n];
    for(int i = 0 ; i<n ; i++) cin>>a[i];
    for(int i = 0 ; i<n-1 ; i++){
      int indx = i;
      for(int j = i+1 ; j<n ; j++){
        if(a[j]<a[indx]) indx = j;
      }
      if(indx != i) {
        int temp = a[indx];
        a[indx] = a[i];
        a[i] = temp;
      }
    }
    for(int i = 0 ; i<n ; i++) cout<<a[i]<<" ";
}

JAVA code:  

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int n = s.nextInt();
      int a[];
      a = new int[n];
      for(int i = 0 ; i<n ; i++) a[i] = s.nextInt();
      for(int i = 0 ; i<n-1 ; i++){
        int indx = i;
        for(int j = i+1 ; j<n ; j++){
          if(a[j]<a[indx]) indx = j;
        }
        if(indx != i) {
          int temp = a[indx];
          a[indx] = a[i];
          a[i] = temp;
        }
      }
      for(int i = 0 ; i<n ; i++) System.out.print(a[i]+" ");
  }
}

Python code

n = int(input())
a = []
for i in range(n):
  x = int(input())
  a.append(x)
for i in range(n-1):
  indx = i
  for j in range(i+1,n):
    if a[j]<a[indx]:
      indx = j
  if indx != i:
    temp = a[indx]
    a[indx] = a[i]
    a[i] = temp
for i in range(n):
  print(a[i],end=' ')

Input: 5
         23 56 32 78 12 

Output: 12 23 32 56 78


The time complexity of the code is O(n2) as here we use the nested for loops.
The space complexity of the code is O(1).

Let’s look at the advantages of the selection sort algorithm.

ADVANTAGES

• As the selection sort algorithm is an in-place algorithm, there is no need for extra space.
• The selection sort algorithm efficiently works over the small set of elements.

Now let’s look at the disadvantages of the bubble sort.

DISADVANTAGES

• The selection sort algorithm is very less efficient likewise the bubble sort as it uses nested loops which increases the time complexity of the code.
• Performance of the selection sort algorithm is also based on the ordering of the elements in the list.

CONCLUSION

That’s it from this tutorial. Hope you guys found It interesting. We have learned about the selection sort algorithm, its implementation, advantages, and disadvantages of the selection sort algorithm and we have solved the selection sort algorithm in different programming languages. Happy coding!