Selection Sort Algorithm in C, in Java, in C++, in Python & Examples

1. What is Selection sort
2. Selection sort Pseudocode
3. Selection sort Algorithm
4. Selection sort Algorithm Dry Run
5. Selection sort Time complexity
6. Selection sort Space complexity
7. Selection sort in C
8. Selection sort in Java
9. Selection sort in C++
10. Selection sort in Python
11. Selection sort Example
12. Selection sort vs Bubble sort vs Insertion sort

What is Selection Sdort

• It is a simple sort algorithm that revolves around the comparison
• In each iteration, one element gets placed
• We choose the minimum element in the array and place is at the beginning of the array by swapping with the front element
• We can also do this by choosing maximum element and placing it at the rear end
• Selection sort basically selects an element in every iteration and place it at the appropriate position

Selection Sort Pseudocode

• Set min  index to the first index of an unsortedddddddddddddddd array
• Iterate the entire unsorted array and do the comparison with min
• If element present at the min is greater than the element present at the current index then update min with a current index
• Once the iteration is complete, swap the element of min index with the first element of the unsorted part
• For descending order, instead of maintaining the smallest element index, maintain the largest element index

Selection sort Algorithm

SelectionSort(arr, n)
  iterate (n - 1) times
  set the first unsorted element index as the min
 	 for each of the unsorted elements
    		if element < currentMin
     			set element's index as new min
 	 swap element at min with first unsorted position
end selectionSort

Selection sort Algorithm Dry Run

Input:

First step – marking of sorted part

After i=1

After i=2

After i=3

After i=4, no iteration is required as the last element is already sorted

Selection sort Time Complexity

• In the worst case, in every iteration, we have to traverse the entire array for finding min elements and this will continue for all n elements. Hence this will perform n^2 operations in total. 
• In the best case that is sorted array, we can do some modification by using lag to check whether the lament is already sorted or not
• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

Selection sort Space Complexity

• No auxiliary space is required in Selection Sort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements
• Hence space complexity is: O(1)

Selection sort in C 

#include <stdio.h>

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

//selection sort function
void selectionSort(int arr[], int n) {
  for (int j = 0; j< n - 1; j++) {
    int min = j;
    for (int i = j + 1; i < n; i++) {

      if (arr[i] < arr[min])
        min = i;
    }

    swap(&arr[min], &arr[j]);
  }
}

void display(int arr[], int n) {
  for (int i = 0; i < n; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main() {
  int arr[] = {20, 12, 10, 15, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  printf("Elements before sorting: \n");
  selectionSort(arr, n);
  printf("Elements after sorting:\n");
  display(arr, n);
}






Output of the program:
Elements before sorting:
2  12  10  15  20  

Elements after sorting:
2  12  10  15  20  

Selection sort in Java

class SelectionSort {
 //selection sort function
 void selectionSort(int arr[]) {
    int size = arr.length;

    for (int j = 0; j < size - 1; j++) {
      int min = j;

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

           if(arr[i]<arr[min])
                min = i;
        
      }

      int tmp = arr[j];
      arr[j] = arr[min];
      arr[min] = tmp;
    }
 }
  
  // method for printing the elements 
  void display(int arr[]) {
     int size = arr.length;
	 for (int i = 0; i < size; i++)
		System.out.print(arr[i]+" ");
	System.out.println();
	
   }

  public static void main(String args[]) {
    int[] arr = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    System.out.println("Elements after sorting: ");
    ss.display(arr);
    ss.selectionSort(arr);
    System.out.println("Elements before sorting: ");
    ss.display(arr);
  }
}




Output of the program:
Elements before sorting:
2  12  10  15  20  

Elements after sorting:
2  12  10  15  20  

Selection sort in C++ 

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

void display(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

//selection sort function
void selectionSort(int arr[], int n) {
  for (int j = 0; j < n - 1; j++) {
    int min = j;
    for (int i = j + 1; i < n; i++) {

      if (arr[i] < arr[min])
        min = i;
    }

    swap(&arr[min], &arr[j]);
  }
}

int main() {
  int arr[] = {20, 12, 10, 15, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Elements before sorting:\n";
  display(arr, n);
  selectionSort(arr, n);
  cout << "Elements after sorting:\n";
  display(arr, n);
}




Output of the program:
Elements before sorting:
2  12  10  15  20  

Elements after sorting:
2  12  10  15  20  

Selection sort in Python

//selection sort function
def selectionSort(arr, n):
   
    for stp in range(n):
        min = stp

        for i in range(stp + 1, n):
         
            if arr[i] < arr[min]:
                min = i
         
        (arr[stp], arr[min]) = (arr[min], arr[stp])


arr = [-2, 45, 0, 11, -9]
n = len(arr)
print('Elements before sorting:')
print(arr)
selectionSort(arr, n)
print('Elements after sorting:')
print(arr)


Output of the program:
Elements before sorting:
2  12  10  15  20  

Elements after sorting:
2  12  10  15  20  

Selection Sort Example

Example1

Find kth smallest element in the array

Input

5

12 45 17 99 34 

2

Output

17

JAVA Code

import java.util.*;

class Solution {
  //selection sort function
 static void findKSmallest(int arr[],int n,int k) {
    if(k>n){
        System.out.println("No such element possible");
        return;        
    }
    
    for (int j = 0; j < k ; j++) {
      int min = j;

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

           if(arr[i]<arr[min])
                min = i;
        
      }

      int tmp = arr[j];
      arr[j] = arr[min];
      arr[min] = tmp;
    }
    System.out.println("answer is : "+arr[k-1]);
 }

  public static void main(String args[]) {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[] arr=new int[n];
    for(int i=0;i<n;i++)
        arr[i]=in.nextInt();
    int k=in.nextInt();
    findKSmallest(arr,n,k);
  }
}

C++ code

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

//selection sort function
void findKSmallest(int arr[], int n, int k) {
 if(k>n){
      printf("No such element possible");
      return;
  }
  for (int j = 0; j < k; j++) {
    int min = j;
    for (int i = j + 1; i < n; i++) {

      if (arr[i] < arr[min])
        min = i;
    }

    swap(&arr[min], &arr[j]);
  }
  
  cout<<arr[k-1];
}

int main() {
  int n,k;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  cin>>k;
  findKSmallest(arr,n,k);
}

C Code

#include <stdio.h>

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

//selection sort function
void findKSmallest(int arr[], int n, int k) {
  if(k>n){
      printf("No such element possible");
      return;
  }
  for (int j = 0; j< k; j++) {
    int min = j;
    for (int i = j + 1; i < n; i++) {

      if (arr[i] < arr[min])
        min = i;
    }

    swap(&arr[min], &arr[j]);
  }
  printf("answer is %d",arr[k-1]);

}



int main() {
  int n,k;
  scanf("%d",&n);
  int arr[n];
  for(int i=0; i<n; i++)
      scanf("%d",&arr[i]);
  scanf("%d",&k);

  findKSmallest(arr, n ,k);
}

Selection sort vs Bubble sort vs Insertion sort

• In terms of algorithm
  • In Insertion sort, adjacent elements are compared and sorted if they are in the wrong order.
  • In the Selection Sort, we select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and the single element is already sorted and we will have array sorted by 1 element in every iteration
  • In Insertion sort, we create partitions of sorted and unsorted parts. One by one element from the sorted art is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.

• In terms of time and space complexity
  • All 3 sorts have O(n2) time complexity. But via flag variables we can reduce the time complexity of Insertion and insertion to O(n) is the best case.
  • Space Complexity is the same for all i.e., O(1)

• In terms of speed
  • Insertion sort may work best with an already sorted array and there is no need for any extra flag.

• In terms of in-place
  • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
  • Selection, Insertion, and Insertion are in-place algorithms and do not require any auxiliary memory.

• In terms of stability
  • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
  • Insertion and Insertion are stable algorithms but the naive selection is not as swapping may cost stability.