Selection Sort Algorithm and its Implementation

Selection sort is the most fundamental, simple and most importantly an in-place sorting algorithm.

This algorithm divides the input list into two sub arrays-

1. A sub array of sorted elements which is empty at the beginning and keep on increasing with each item added to it.
2. An unsorted sub array of remaining elements. This is equal to the input size in the beginning and its size reduces to zero as we reach the end of algorithm.

The basic idea is that in each iteration of this algorithm we pick an element (either largest or smallest, this depends on the sorting scenario) and appends it to the sorted element list, reducing the size of unsorted list by one.

Let’s understand it with an example-

Yellow – Sorted part of the list
Red – Key selected from the unsorted list, which is the smallest element of unsorted subarray in this case
Blue – This element in unsorted subarray, which is compared with the selected key (in red).
Double headed Arrow – Show the elements swapped

So in the above picture we can see that in each iteration we choose the smallest element from the unsorted sub array and swaps it with the first element of unsorted sub array due to which sorted sub array keeps on increasing in size until complete array is sorted.

Iterative Pseudocode:

selectionSort(array a)
     //Search for the minimum element and adds to the sorted sub array
    for i in 0 -> a.length - 2 do
        minIndex = i

	//Find minimum element in the remaining sub array and update the minIndex
        for j in (i + 1) -> (a.length - 1) do
            if a[j] < a[minIndex]
                minIndex = j

	//Swap the minimum value find with the first element of unsorted subarray
        swap(a[i], a[minIndex])

Asymptotic Analysis

Since this algorithm contains two nested loops and none of the iteration depends on the value of the items in the array it is easy to find the complexity of this algorithm. To find first element it requires (n-1) comparisons, for second element (n-2) and so on. So for (n ? 1) + (n ? 2) + … + 2 + 1 = n(n ? 1) / 2 ? ?(n²) comparisons. Summarizing all this –

Data structure used -> Array
Time Complexity (Best, worst and average case) -> O(n²)
Worst case space complexity -> O(n) total space, O(1) Auxiliary space

ITERATIVE Implementation of Selection sort in C programming language

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

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

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

    // After every iteration size of sorted array increases by one
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        minIndex = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[minIndex])
            minIndex = j;

        // Swap the found minimum element with the first element
        swap(&arr[minIndex], &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("
");
}

// Main function to test above implemented methods
int main()
{
    int arr[] = {9, 4, 2, 3, 6, 5, 7, 1, 8, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: 
");
    printArray(arr, n);
    return 0;
}

Output:-

Sorted array: 
0 1 2 3 4 5 6 7 8 9 

Implementation of Selection Sort Algorithm in Java

package com.codingeek.algorithms.sorting;

public class SelectionSortAlgorithm {

	//Main method to launch program
	public static void main(String a[]) {
		int[] arr1 = { 9, 4, 2, 3, 6, 5, 7, 1, 8, 0};
		doSelectionSort(arr1);
		printArray(arr1);
	}

	// This method sorts the input array
	public static void doSelectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int index_min = i;
			// Search for the minimum element in unsorted array
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[index_min]) {
					index_min = j;
				}
			}
			//Swap minimum element with element at index i
			swapNumbers(arr, i, index_min);
		}
	}

	//Swap numbers in the given array
	private static void swapNumbers(int[] arr, int i, int index) {
		int smallerNumber = arr[index];
		arr[index] = arr[i];
		arr[i] = smallerNumber;
	}

	//prints array
	private static void printArray(int[] arr2) {
		System.out.println("Sorted Array - ");
		for (int i : arr2) {
			System.out.print(i + " ");
		}
	}
}

Output:-

Sorted array: 
0 1 2 3 4 5 6 7 8 9 

Comparison to other O(n²) sorting Algorithms

While comparing to Bubble Sort, Selection sort is better in every scenario as it has same number of comparison but write operations are lot less as compared to Bubble Sort.
While considering Insertion Sort it is observed that insertion sort generally makes half number of comparisons as made by the selection sort as Insertion sort scans only the required number of elements to find the correct place for the required element whereas Selection sort scans completely every time. But this behavior of Insertion sort makes is less stable and its time changes greatly with the order of input. Moreover if performing swap (or memory operation) operation is more costly than comparison than Selection sort outperforms Insertion as Insertion sort requires O(n²) swaps where as Selection sort requires O(n) swaps.

Do share the wisdom and share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning.. Happy Learning.. 🙂

Recommended -