CS Review: Selection Sort
The previous sorting algorithm we took a look at was bubble sort. This time around we will be taking a look at selection sort, which is slightly more complex than bubble sort, but only by a tiny bit.
The idea behind selection sort is that you keep iterating over your array of data, finding the minimum element each time and placing it at the start of the list. In this way, you can think of selection sort as managing two subarrays: the portion of the array that is sorted and the portion that still needs to be sorted.
Like bubble sort, selection sort has a worst-case time complexity of O(n2), but it does have a tendency to outperform bubble sort. Selection sort also has a nice side-effect where it will never do more than O(n) swaps, which is nice if you’re operating in an environment in which memory writes are costly.
Implementation
Much like bubble sort, I think the clearest explanation of this algorithm is to simply look at its implementation, so here it is in Java:
1package com.hackeradam.sorting;
2public class Main {
3 public static void selectionSort(int arr[]) {
4 int smallestIdx; // Stores the index of the minimum value
5 int tmp;
6 for (int i = 0; i < arr.length - 1; i++) {
7 smallestIdx = i;
8 // Locate the smallest items
9 for (int j = i + 1; j < arr.length; j++) {
10 if (arr[j] < arr[smallestIdx])
11 smallestIdx = j;
12 }
13 // Perform the swap
14 tmp = arr[i];
15 arr[i] = arr[smallestIdx];
16 arr[smallestIdx] = tmp;
17 }
18 }
19 public static void printArray(int arr[]) {
20 for (int i=0; i < arr.length; i++) {
21 System.out.print(arr[i] + " ");
22 }
23 System.out.println();
24 }
25 public static void main(String... args) {
26 int items[] = {5, 2, 88, 100, 3, 0, -1, 20, 30, 7, 99};
27 printArray(items);
28 System.out.println("After selection sort: ");
29 bubblesort(items);
30 printArray(items);
31 }
32}