Definition

Selection sort algorithm is a simple sorting algorithm. Selection sort algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The algorithm maintains two subarrays in a given array.

• The subarray which already sorted. 
• The remaining subarray was unsorted.

In every iteration of the selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. 

Flowchart of Selection sort

How selection sort works?

Follow the below steps to solve the problem:

• Set minimum value(min_index) to location 0.
• Traverse the array to find the minimum element in the array.
• If any element smaller than (min_index) is found then swap both the values.
• Increment (min_index) to point to the next element.
• Repeat until the array is sorted.

Below is the implementation of the above approach in multiple programming languages such as Golang, Python, Javascript, C, C++ etc.

Implementation

Golang

package main

import (
    "fmt"
)

func selectionSort(arr []int) {
    var i, j, min_index int
    for i = 0; i < len(arr)-1; i++ {
        min_index = i
        for j = i + 1; j < len(arr); j++ {
            if arr[j] < arr[min_index] {
                min_index = j
            }
        }

        // if min_index is not equals to i then swap the indexes
        if min_index != i {
            arr[i], arr[min_index] = arr[min_index], arr[i]
        }
    }
}

func main() {
    arr := []int{12, 23, 34, 43, 4, 34, 24, 3, 53, 25454, 64}
    fmt.Println("before selection sort", arr)
    selectionSort(arr)
    fmt.Println("after selection sort", arr)
}

Python

def selectionSort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1,len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i],arr[min_index] = arr[min_index],arr[i]



arr = [12, 23, 34, 43, 4, 34, 24, 3, 53, 25454, 64]
print("before selection sort",arr)
selectionSort(arr)
print("after selection sort",arr)

Javascript

function selectionSort(arr) {
  var i, j, min_index;
  for (i = 0; i < arr.length - 1; i++) {
    min_index = i;
    for (j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min_index]) {
          min_index = j;
      }
    }

    if (min_index != i) {
      var temp = arr[i];
      arr[i] = arr[min_index];
      arr[min_index] = temp;
    }
  }
}


var arr = [12, 23, 34, 43, 4, 34, 24, 3, 53, 25454, 64];

console.log("before selection sort", arr);
selectionSort(arr);
console.log("after selection sort", arr);

C Language

// C program for implementation of selection sort
#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void selectionSort(int arr[], int n) {
  int i, j, min_idx;

  // One by one move boundary of unsorted subarray
  for (i = 0; i < n - 1; i++) {
    // Find the minimum element in unsorted array
    min_idx = i;
    for (j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;

    // Swap the found minimum element with the first element
    if (min_idx != i)
      swap(&arr[min_idx], &arr[i]);
  }
}

/* Function to print an array */
void printArray(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// Driver program to test above functions
int main() {
  int arr[] = {12, 23, 34, 43, 4, 34, 24, 3, 53, 25454, 64};
  int n = sizeof(arr) / sizeof(arr[0]);
  printf("before selection sort: ");
  printArray(arr, n);
  selectionSort(arr, n);
  printf("after selection sort: ");
  printArray(arr, n);
  return 0;
}

C++

// C program for implementation of selection sort
#include <bits/stdc++.h>
using namespace std;

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void selectionSort(int arr[], int n) {
  int i, j, min_idx;

  // One by one move boundary of unsorted subarray
  for (i = 0; i < n - 1; i++) {
    // Find the minimum element in unsorted array
    min_idx = i;
    for (j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;

    // Swap the found minimum element with the first element
    if (min_idx != i)
      swap(&arr[min_idx], &arr[i]);
  }
}

/* Function to print an array */
void printArray(int arr[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

// Driver program to test above functions
int main() {
  int arr[] = {12, 23, 34, 43, 4, 34, 24, 3, 53, 25454, 64};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  cout << "before selection sort: ";
  printArray(arr, n);
  
  selectionSort(arr, n);
  cout << "after selection sort: ";
  printArray(arr, n);
  
  return 0;
}

Output:

before selection sort [12 23 34 43 4 34 24 3 53 25454 64]
after selection sort [3 4 12 23 24 34 34 43 53 64 25454]

Complexity Analysis of Selection Sort

Time Complexity: The time complexity of Selection Sort is O(N²) as there are two nested loops:

• One loop to select an element of Array one by one = O(N)
• Another loop to compare that element with every other Array element = O(N)

Overall complexity = O(N) * O(N) = O(N*N) = O(N²)

Auxiliary Space: O(1) as the only extra memory used is for temporary variables while swapping two values in Array. The selection sort never makes more than O(N) swaps and can be useful when memory write is a costly operation.

Live Codebase Links are mentioned below:
Golang
Python
Javascript
C Language
C++

Please write comment if you find anything wrong, or if you want to share more information about the topic explained in this post.