Selection Sort

Selection sort is a sorting algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning of the unsorted part. This is a simple yet effective algorithm with a worst-case time complexity of $O(N^2)$ and a constant space complexity $O(1)$.

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Selection Sort is used when:

  • Only O(N) swaps can be made or is a requirement
  • When memory write is a costly operation in terms of time or hardware durability

Algorithm


The algorithm maintains two subarrays in a given array:

  • The subarray which is already sorted.
  • Remaining subarray which is unsorted.

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


Example


Input data: 12, 1, 99, 5

We will maintain two arrays: Sorted and Unsorted. 

Iteration 0: 

Sorted: -
Unsorted: 12, 1, 99, 5

Iteration 1: 

Minimum element in Unsorted part: 1

Sorted: 1
Unsorted: 12, 99, 5

Iteration 2: 

Minimum element in Unsorted part: 5

Sorted: 1, 5
Unsorted: 12, 99

Iteration 3: 

Minimum element in Unsorted part: 12

Sorted: 1, 5, 12
Unsorted: 99

Iteration 4: 

Minimum element in Unsorted part: 99

Sorted: 1, 5, 12, 99
Unsorted: -

Unsorted part is empty hence, the input data is sorted.

Sorted output: 1, 5, 12, 99

Complexity


The complexity of Selection Sort is as follows:

  • Worst case time complexity: $O(N^2)$ comparisons and $O(N)$ swaps
  • Average case time complexity: $O(N^2)$ comparisons and $O(N)$ swaps
  • Best case time complexity: $O(N^2)$ comparisons and $O(N)$ swaps
  • Space complexity: $O(1)$ auxillary space

Pseudocode

The pseudocode of Selection Sort is as follows:

SelectionSort(A):
  for j ← 1 to n-1
    smallest ← j
    for i ← j + 1 to n
      if A[i] < A[smallest]
        smallest ← i
    Swap A[j] ↔ A[smallest]

Implementations

Implementation of exponential search algorithm in 9 languages that includes C, C++, Java, Go, JavaScript, PHP, Python, Rust and Swift.

  • C
  • C++
  • CSharp
  • Java
  • Go

C

  
#include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
int main()
{
    int n, i, j, min, temp;    
    printf("\n Enter the number of Elements: ");
    scanf("%d",&n);
    int a[n];
    printf("\n Enter thr %d Elements: ",n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);     
    for (i = 0; i < n - 1; i++)
    {
        min = i;
        for (j = i + 1; j < n; j++)
        {
            if (a[min] > a[j])
                min = j;
        }
        if (min != i)
        {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }     
    printf("\n The Sorted array is : ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

C++


/*
Part of Cosmos by OpenGenus Foundation
selection sort synopsis
template<typename _Input_Iter, typename _Compare>
void
selectionSort(_Input_Iter begin, _Input_Iter end, _Compare compare);
template<typename _Input_Iter>
void
selectionSort(_Input_Iter begin, _Input_Iter end);
 */
#include <functional>
template<typename _Input_Iter, typename _Compare>
void
selectionSort(_Input_Iter begin, _Input_Iter end, _Compare compare)
{
    if (begin != end)
    {
        for (auto curr = begin; curr != end; ++curr)
        {
            auto minimum = curr;
            auto forward = curr;
            while (++forward != end)
                if (compare(*forward, *minimum))
                    minimum = forward;
            std::iter_swap(minimum, curr);
        }
    }
}
template<typename _Input_Iter>
void
selectionSort(_Input_Iter begin, _Input_Iter end)
{
    using value_type = typename std::iterator_traits<_Input_Iter>::value_type;
selectionSort(begin, end, std::less&lt;value_type&gt;());

}

C#


// Part of Cosmos by OpenGenus Foundation
public class SelectionSort
{
    public static void Main(string[] args)
    {
        int[] items = new int[] {52, 62, 143, 73, 22, 26, 27, 14, 62, 84, 15 };
        Sort(items);     
        System.Console.WriteLine("Sorted: ");
        for (int i = 0; i < items.Length; i++)
            System.Console.Write(items[i] + " ");
    }
    private static void Sort(int[] items)
    {
        for (int i = 0; i < items.Length - 1; i++)
        {
            int minIndex = i;            
            for (int j = i + 1; j < items.Length; j++)
                if (items[j] < items[minIndex])
                    minIndex = j;              
            int temp = items[minIndex];
            items[minIndex] = items[i];
            items[i] = temp;
        }
    }
}

Java


  /**
 * Utility class for sorting an array using Selection Sort algorithm. Selection
 * Sort is a basic algorithm for sorting with O(n^2) time complexity. Basic idea
 * of this algorithm is to find a local minimum, which is the minimum value from
 * (i+1) to length of the array [i+1, arr.length), and swap it with the current
 * working index (i).
 *
 * Part of Cosmos by OpenGenus Foundation
 */
class SelectionSort {
  /**
   * Example usage.
   */
  public static void main(String[] args) {
        int[] arr = { 1, 5, 2, 5, 2, 9, 7 };
        SelectionSort.sort(arr);
        System.out.print(java.util.Arrays.toString(arr));
    }
    /**
     * Sort an array using Selection Sort algorithm.
     *
     * @param arr
     *            is an array to be sorted
     */
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                /* find local min */
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }
    /**
     * Utility method for swapping elements in an array.
     *
     * @param arr
     *            is an array to be swapped
     * @param i
     *            is index of first element
     * @param j
     *            is index of second element
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Go


package main
// Selection Sort in Golang
// Part of Cosmos by OpenGenus Foundation
import "fmt"
func selectionSort(array [8]int) [8]int {
    for i := 0; i < len(array); i++ {
        min := i
        for j := i + 1; j < len(array); j++ {
            if array[j] < array[min] {
                min = j
            }
        }
        array[i], array[min] = array[min], array[i]
    }
    return array
}
func main() {
    array := [8]int{5, 6, 1, 2, 7, 9, 8, 4}
    sorted := selectionSort(array)
    fmt.Printf("%v\n", sorted)
}

Applications

The applications of Selection Sort is as follows:

  • Selection sort almost always outperforms bubble sort and gnome sort.

  • Can be useful when memory write is a costly operation.

  • While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n^2) swaps).

  • It almost always far exceeds the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes.

  • This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.

Flash Memory