# Selection Sort

#### Sorting Algorithms selection sort Algorithms Get FREE domain for 1st year and build your brand new site

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

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&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 int) 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 := 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.  #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.