Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 20 minutes | Coding time: 10 minutes
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.
Complexity
The complexity of Selection Sort is as follows:
- Worst case time complexity:
Θ(N^2)comparisons andΘ(N)swaps - Average case time complexity:
Θ(N^2)comparisons andΘ(N)swaps - Best case time complexity:
Θ(N^2)comparisons andΘ(N)swaps - Space complexity:
Θ(1)auxillary space
Read ahead and make sense of the complexity denoted above
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
Step 1: Find the smallest element in the unsorted array (N)
Step 2: Move the smallest element to the front of the unsorted array and move the element at the front to the location of the smallest element
Step 3: Follow step 1 to 2 for the rest of the elements (N-1)
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
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<value_type>());
}
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.
