Selection Sort in Data Structure

Selection sort is a simple sorting where the control searches for the smallest element and puts it in the first index. In each iteration, it searches for the smallest element and puts it in its correct final position. The position of sorted elements does not change after swapping.

• Selection sort is an unstable algorithm
• Modification of Selection sort is possible to be a stable algorithm.

Procedure for Selection Sort

1. Swap the first element with the smallest element in the array. We have now n-1 elements to sort

2. Find the smallest element in array from array[1] to array [n-1] and swap it with the second position

3. For the next element, find the smallest element in the remaining array and swap it.

Selection Sort Algorithm

Step 1:  for k = 1 to n-1
step 2: set small = arr[k]
step 3: set pos = k
step 4: repeat for j = k+1 to n -1
             if small > arr[j]
             set small = arr[j]
             set pos = j
            [end of if]
            [end of loop]
step 5: swap a[k] with arr[pos]
            [end of loop]
step 6: Stop

Pseudocode for Selection Sort

selectionSort(array):
     for i=0 to length(array):
     Minimum element  = array[0]
           for each unsorted elements:
                   if element < Minimum element
           element = new minimum
      swap minimum element with first unsorted position
end selectionSort

Working of Selection Sort

Let’s Sort the following array by the insertion sort technique.

1st Iteration:

2nd Iteration:

3rd Iteration:

4th Iteration:

5th Iteration:

6th Iteration:

7th Iteration:

8th Iteration:

In the above example, we can see the change in the order of three elements with the same value of ‘9’ after sorting. Hence we can conclude that selection sort is not a stable algorithm.

Selection sort implementation in C

#include<stdio.h>  
int smallest_element(int[],int,int); 

void main ()  
{  
    int a[] = {32, 6, 76, 52, 29, 11, 94, 62, 73, 81};  
    int i,pos,temp;  
    for(i=0;i<10;i++)  
    {  
        pos = smallest_element(a,10,i);  
        temp = a[i];  
        a[i]=a[pos];  
        a[pos] = temp;  
    }  
    printf("sorted array:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",a[i]);  
    }  
}  
int smallest_element(int a[], int n, int i)  
{  
    int smallest,position,j;  
    smallest = a[i];  
    position = i;  
    for(j=i+1;j<10;j++)  
    {  
        if(a[j]<smallest)  
        {  
            smallest = a[j];  
            position=j;  
        }  
    }  
    return position;  
}  

Selection sort implementation C++

#include<iostream>
using namespace std;
int smallest_element(int[],int,int); 

int main ()  
{  
    int a[] = {32, 6, 76, 52, 29, 11, 94, 62, 73, 81};  
    int i,pos,temp;  
    for(i=0;i<10;i++)  
    {  
        pos = smallest_element(a,10,i);  
        temp = a[i];  
        a[i]=a[pos];  
        a[pos] = temp;  
    }  
    cout << "sorted array:\n";  
    for(i=0;i<10;i++)  
    {  
        cout << " " << a[i];  
    }  
}  
int smallest_element(int a[], int n, int i)  
{  
    int smallest,position,j;  
    smallest = a[i];  
    position = i;  
    for(j=i+1;j<10;j++)  
    {  
        if(a[j]<smallest)  
        {  
            smallest = a[j];  
            position=j;  
        }  
    }  
    return position;  
}  

Implementation of Selection Sort in JAVA

public class SelectionSort 
{
  void selectionSort(int array[]) 
  {
    int len = array.length;

    for (int j = 0; j < len - 1; j++) 
    {
      int min_pos = j;

      for (int i = j + 1; i < len; i++) 
      {

        if (array[i] < array[min_pos]) 
        {
          min_pos= i;
        }
      }
      
      int temp = array[j];
      array[j] = array[min_pos];
      array[min_pos] = temp;
    }
    System.out.println("Sorted Array: ");
    for (int i = 0; i < len; i++) 
    {
        System.out.print(array[i] +" ");
        
    }
    
  }

  public static void main(String args[]) 
  {
    int[] array = { 32, 6, 76, 52, 29, 11, 94, 62, 73, 81 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(array);
    
    
  }
}

Selection sort implementation in Python

def selectionSort(array, length):
   
    for i in range(length):
        min_pos = i

        for j in range(i + 1, length):
         
            if array[j] < array[min_pos]:
                min_pos = j
         
        (array[i], array[min_pos]) = (array[min_pos], array[i])


array = [32, 6, 76, 52, 29, 11, 94, 62, 73, 81]
length = len(array)
selectionSort(array, length)
print('Sorted Array:')
print(array)

Complexity of Selection Sort

Total number of comparison :

(n-1) + (n-2) + (n-3) ………. + 1

= n(n-1)/2 ≈ n^2 ( complexity)

1. Best Case Complexity

Array is already sorted.

2. Average Case Complexity

elements in the array are jumbled i.e. they are neither in ascending or descending order.

3. Worst-Case Complexity

Array is sorted in the opposite of the required order.

4. Space complexity

An extra variable, temp, is used to swap the variables.

Applications of Selection Sort

Selection sort can be used:

1. when a small dataset needs to be sorted

2. in algorithms where the cost of swapping does not matter.

3. in scenarios where there is a need to check all elements.

4. In situations where the cost of writing in flash memory matters. It has a write/swap complexity of O(n) while that of bubble sort is O(n^2).

Conclusion

Selection sort is an unstable algorithm that is good for sorting small datasets. Time taken by this algorithm is more but it is beneficial to scenarios where we have memory limitations. Selection sort is simple and easy to implement. In further articles, we see other sorting techniques which are based on different algorithms techniques.