Selection Sort Algorithm

In this tutorial, you will learn how selection sort works. Also, you will find working examples of selection sort in C, C++, Java and Python.

Selection Sort is an algorithm that works by putting the smallest element in the first position and then putting the second smallest element at the second position and so on (for ascending order).


Pseudocode

selectionSort(array, size)
  for step < 1 to size- 1
    min <- i
    for i <- step+1 to size
      if array[i] < list[min]
        min = i
      end if
    end for
    swap array[min] and array[step]
  end for
end selectionSort

How Selection Sort Works?

At every pass, the smallest element is chosen and swapped with the leftmost unsorted element. Let us analyze the working of the algorithm with the help of the following illustration.

Selection Sort Steps Selection Sort Steps Selection Sort Steps Selection Sort Steps

Here, size=5.

  1. Inside the first loop (before entering the second loop), the leftmost unsorted element is considered as the smallest element. (min=1st element=20)
  2. When step=0 (ie. the first pass of the first loop) and i=step+1=0+1=1(ie. the first pass of the second loop), min and the 2nd element are compared (ie. 20 and 12 are compared)
  3. When step=0 and i=2, min is compared with the 3rd element (ie. 12 is compared with 10)
    If the 3rd element is smaller than min then, min is changed to the 3rd element. (ie. min=10)
    If min is already the smaller one then, nothing is done.
  4. When step=0and i=3, ………………
  5. When step=0 and i=4, min=2.
  6. Swap min with the leftmost unsorted element (ie. 20).
  7. When step=1 and i=2,.............
  8. The process continues till the array is sorted.

Selection Sort in C

#include <stdio.h>

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]);
  } 
}
void printArray(int array[], int size){
  for(int i=0; i<size; ++i){
    printf("%d  ", array[i]);
  }
  printf("\n");
}
int main(){
  int data[]={20, 12, 10 ,15, 2};
  int size=sizeof(data)/sizeof(data[0]);
  selectionSort(data, size);
  printf("Sorted array in Acsending Order:\n");
  printArray(data, size);
}    

Selection Sort in C++

#include <iostream> 
using namespace std;

void swap(int *a, int *b){ 
  int temp = *a;
  *a = *b;
  *b = temp;
} 
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[]={20, 12, 10 ,15, 2};
  int size=sizeof(data)/sizeof(data[0]);
  selectionSort(data, size); 
  cout<<"Sorted array in Acsending Order:\n";
  printArray(data, size);
}

Selection Sort in Python

def selectionSort(array):
    for step in range(len(array)):
	min_idx = step
	for i in range(step+1, len(array)):
	    if array[i] < array[min_idx]: 
		min_idx = i
	array[step], array[min_idx] = array[min_idx], array[step]

data = [20, 12, 10 ,15, 2]
selectionSort(data)
print("Sorted Array in Ascending Order:")
print(data)

Selection Sort in Java

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;
    }
  }
  void printArray(int array[]){
    int size=array.length;
    for(int i=0; i<size; ++i)
      System.out.print(array[i]+" ");
    System.out.println();
  }
  public static void main(String args[]){
    int[] data={20, 12, 10 ,15, 2};
    SelectionSort ss=new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    ss.printArray(data);
  }
}

Complexity

Pass Number of Comparison
1st (n-1)
2nd (n-2)
3rd (n-3)
... ...
last 1

Number of comparisons:(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2 nearly equals to n2

Complexity = O(n2)

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n2.

Time Complexities:

  • Worst Case Complexity: O(n2)
    If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
  • Best Case Complexity: O(n2)
  • Average Case Complexity: O(n2)
    It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

The time complexity of selection sort is the same in all cases. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached. Following table shows the count at each step.

Space Complexity:

Space complexity is O(1) because an extra variable temp is used.


Selection Sort Applications

The selection sort is used when:

  • small list is to be sorted
  • cost of swapping does not matter
  • checking of all the elements is compulsory
  • cost of writing to a memory matters like in flash memory (number of writes(swap) is O(n) as compared to O(n2) of bubble sort)