Selection sort is noted for its simplicity, specially an in-place comparison sort. It has O(n^2) time complexity, inefficient on larger lists.

The algorithm proceeds to find out the minimum element from the list and exchanged with the left most element and similarly finds second minimum element and exchanged with the second left element and so on.

This algorithm is called selection sort because it repeatedly selects the next-smallest element and swaps it into place.

Let’s understand the algorithm through pseudo code and see the steps.

Pseudo Code:

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

Algorithm Steps :

Algorithm Steps

Implementation:

C

# Selection sort in C
#include <stdio.h>
// Function for swapping array 
void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
void selectionSort(int array[], int size)
{
  for (int step = 0; step < size - 1; step++)
  {
    int min_idx = step;
    for (int i = step + 1; i < size; i++)
    {
      if (array[i] < array[min_idx])
        min_idx = i;
    }
    swap(&array[min_idx], &array[step]);
  }
}
// Function for printing array
void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
  {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
int main()
{
  int data[] = {2 , 11 , 5 ,2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("Selection Sort \n");
  printArray(data, size);
}

Java

import java.util.Arrays;

class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;
    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;
      for (int i = step + 1; i < size; i++) {
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Selction Sort: ");
    System.out.println(Arrays.toString(data));
  }
}

Python

def selectionSort(array, size):
    for step in range(size):
        min_idx = step
        for i in range(step + 1, size):
            # To sort in descending order, change > to <.
            if array[i] < array[min_idx]:
                min_idx = i
        (array[step], array[min_idx]) = (array[min_idx], array[step])

data = [2, 11, 5, 2]
size = len(data)
selectionSort(data, size)
print('Selection Sort:\n')
print(data)

C++

/* Selection sort in C++ */

#include <iostream>
using namespace std;
/* Function for swapping array position */
void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
/* Function for printing array */
void printArray(int array[], int size)
{
  for (int i = 0; i < size; i++)
  {
    cout << array[i] << " ";
  }
  cout << endl;
}
void selectionSort(int array[], int size)
{
  for (int step = 0; step < size - 1; step++)
  {
    int min_idx = step;
    for (int i = step + 1; i < size; i++)
    {
      if (array[i] < array[min_idx])
        min_idx = i;
    }
    swap(&array[min_idx], &array[step]);
  }
}
int main()
{
  int data[] = {2, 11, 5, 2};
  /* Calculating size of a particular array. */
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  cout << "Sorted array in Acsending Order:\n";
  printArray(data, size);
}

Few Interview questions on Selection Sort:

Question-What will be the time complexity of selection sort in worst case?

Answer: The time complexity will be O(n^2) .

Question– Explain Selection Sort in layman’s term ?

Answer:

  • Find the smallest element. Swap it with the first element.
  • Find the second-smallest element. Swap it with the second element.
  • Find the third-smallest element. Swap it with the third element.
  • Repeat finding the next-smallest element, and swapping it into the correct position until the array is sorted.

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Thanks Abhijeet Gupta for helping us to grow day by day. Abhijeet is expert in Data Structure and loves to solve competitive problems.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert