**Selection Sort** is an intuitive sorting algorithm. It’s not the fastest algorithm, but a good starting point when learning about sorting. Also, due to its simplicity, it can be used to verify implementations of harder sorting algorithms. Let’s see how it works!

# How it works

The sorting algorithm consists of 3 parts:

- Iterate over the input data.
- Find the index of the smallest number (
*selection*), starting from the current position up to the end of the given array. - Swap the smallest element with the one at current position.

Let’s see how that looks in the code!

# Selection Sort implementation

The central part of the algorithm is just the execution of the above 3 steps:

1
2
3
4
5
6
7
8
9
10
11

public void sort(int[] values) {
// 1. Iteration over the input data
for (int i = 0; i < values.length; i++) {
// 2. Find the index of the smallest element
int minPos = indexOfMinimum(values, i);
// 3. Move the smallest element into the current position
swap(values, i, minPos);
}
}

To find the smallest value (minimum) in the rest of the elements, we just compare the current minimum `values[minPos]`

with the currently seen element `values[i]`

. If the value under the index `i`

is smaller, we take it as the current index of the smallest element `minPos`

:

1
2
3
4
5
6
7
8
9

private int indexOfMinimum(int[] values, int i) {
int minPos = i;
for (; i < values.length; ++i) {
if (values[i] < values[minPos]) {
minPos = i;
}
}
return minPos;
}

And the swap of elements under the given indices - `first`

and `second`

:

1
2
3
4
5

private void swap(int[] values, int first, int second) {
int tmp = values[first];
values[first] = values[second];
values[second] = tmp;
}

Notice that all parts of the algorithm we’ve implemented in separate methods. This make the code more readable and is a good style.

If you are worried about the cost of calling methods in a loop, then no need to. *JVM Hot-Spot* is taking care of that and will optimize (e.g. inline methods) code where needed. Better focus on writing readable code!

# Testing the implementation

Let’s write a couple of JUnit tests to make sure that our implementation of Selection Sort behaves correctly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;
public class SelectionSortTest {
private SelectionSorter sorter = new SelectionSorter();
@Test
public void shouldDoNothingWithEmptyArray() {
int[] values = {};
sorter.sort(values);
}
@Test
public void shouldDoNothingWithOneElementArray() {
int[] values = {42};
sorter.sort(values);
assertArrayEquals(new int[] {42}, values);
}
@Test
public void shouldSortValues() {
int[] values = { 9, -3, 5, 0, 1};
int[] expectedOrder = { -3, 0, 1, 5, 9};
sorter.sort(values);
assertArrayEquals(expectedOrder, values);
}
}

# Selection Sort properties

- The running time is
**ϴ(n²)**(Big Theta n²), which means that it won’t run faster nor slower than*n²*, - Selection (
`indexOfMinimum`

method) will be executed`n²/2 + n/2`

times, - Memory complexity is
**O(1)**(constant), because the algorithm reuses the input array.

# References

- Binary Search is expecting to receive sorted data