Selection Sort

In this tutorial we will learn about Selection sort algorithm.

About Selection Sort

In this technique we find the smallest element in each pass and place it in the appropriate position to get the elements in ascending or descending order.

In pass 1, smallest element is searched between a[0] to a[n-1] and swapped with a[0].

In pass 2, smallest element is searched between a[1] to a[n-1] and swapped with a[1].

In a similar way the process is carried out n-1 times.

• Selection sort requires n – 1 pass to sort an array of n elements.
• In each pass we search for the smallest element from the search range and swap it with appropriate place.
• In each pass we have n – k comparisons, where n is the number of elements and k is the pass number.
  So, 1st pass requires n – 1 comparisons,
  kth pass requires n – k comparisons and
  the last pass requires 1 comparison.

Algorithm

/**
 * a[0:n-1] is an array of n elements.
 * temp is a variable to facilitate exchange.
 */
SelectionSort(a,n)
Begin
    for k = 1 to n-1 by 1 do  //this is for pass
        Set small = a[k-1];
        Set pos = k-1;
        for j = k to n-1 by 1 do  //this is for searching small element
            if(a[j] < small) then
                Set small = a[j];
                Set pos = j;
            endif
        endfor
        if(pos != k-1) then  //swap value
            Set temp = a[k-1];
            Set a[k-1] = a[pos];
            Set a[pos] = temp;
        endif
     endfor
End

Code in C

#include <stdio.h>

//function declaration
void selectionSort(int *a, int n);

int main(){
  //variable declaration
  int arr[5], i;
  
  //input
  for(i = 0; i < 5; i++)
    scanf("%d", &arr[i]);
  
  //sort
  selectionSort(arr, 5);  //passing arr address and no. of elements
  
  //output
  for(i = 0; i < 5; i++)
    printf("%d\n", arr[i]);
    
  return 0;
}

//function definition
void selectionSort(int *a, int n){
  int k, j, pos, small, temp;
  for(k = 1; k <= n-1; k++){
    small = a[k-1];
    pos = k-1;
    for(j = k; j <= n-1; j++){
      if(a[j] < small){
        small = a[j];
        pos = j;
      }
    }
    if(pos != k-1){
      temp = a[k-1];
      a[k-1] = a[pos];
      a[pos] = temp;
    }
  }
}

Time complexity

1st pass requires (n-1) comparison
2nd pass required (n-2) comparison
... last pass requires 1 comparison.

So, total comparison = (n-1) + (n-2) + ... + 1
= n(n-1)/2
= O(n²)