Selection Sort in Java
Post
Cancel

# Selection Sort in Java

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:

1. Iterate over the input data.
2. Find the index of the smallest number (selection), starting from the current position up to the end of the given array.
3. 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 ,
• Selection (`indexOfMinimum` method) will be executed `n²/2 + n/2` times,
• Memory complexity is O(1) (constant), because the algorithm reuses the input array.