Selection Sort Algorithm

What is Selection Sort?

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest element from the unsorted portion of the array and moving it to the sorted portion of the array.

Steps involved in Selection Sort

• Find the smallest element: First, go through the entire list and find the smallest element.

• Swap: Once you find the smallest element, replace it with the first element of the list.

• Repeat: Now, consider the rest of the list (except the first element you just sorted) and repeat the process until the entire list is sorted

Let's illustrate with an example, consider an array

First Pass: Find the smallest element of the array that is 6 and replace it with the first element of the array.

Second Pass: Find the smallest element in the unsorted section of the array which is 8 and replace it with the first element of the unsorted array.

Third Pass: Find the smallest element in the unsorted section of the array which is 9 and replace it with the first element of the unsorted array.

Fourth Pass: Find the smallest element in the unsorted section of the array which is 10 and replace it with the first element of the unsorted array.

Fifth Pass: Find the smallest element in the unsorted section of the array which is 15 and replace it with the first element of the unsorted array.

Sixth Pass: Find the smallest element in the unsorted section of the array which is 20 and replace it with the first element of the unsorted array.Seventh Pass: Find the smallest element in the unsorted section of the array which is 22 and replace it with the first element of the unsorted array.

Check out the implementation of the above approach in C Programming language.

#include <stdio.h>

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

void selectionSort(int arr[], int n) {
	int i, j, k;
    // i is to track the separation of sorted and unsorted section of array.
    // j is to traverse the unsorted array to find smallest element of the array.
    // k is to store the index of smallest element of the unsorted array for swapping.

	for (i = 0; i < n-1; i++)
	{
		// Find the minimum element in unsorted array
		k = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[k])
			k = j;

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

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

int main() {
	int arr[] = {20, 22, 8, 6, 10, 15, 9};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	printf("Sorted array: \n");
	printArray(arr, n);
	return 0;
}

Time Complexity of the Selection Sort is O(n²).

Check out the comparison of all sorting algorithms to learn more.