Selection Sort

Linear search (contains) was our first classic algorithm. Let’s look at a second classic: sorting, arranging the elements in order from smallest to largest.

We will use selection sort, which works like this:

1. Find the smallest element.
2. Put it in the first position.
3. Find the smallest of what is left, put it second.
4. Keep going until everything is in place.

At each step we select the smallest remaining element and move it into position, which is where the name comes from.

Let’s trace it on [42, 7, 25, 10]. Each pass fills one position, and start is the position that pass is filling. Nothing is sorted yet, so the first pass fills position 0.

┌────┬────┬────┬────┐
│ 42 │  7 │ 25 │ 10 │
└────┴────┴────┴────┘
   ↑
start = 0

The first pass scans all four elements, finds the smallest, 7, and swaps it with 42 in position 0. The shaded cell is the sorted part. Position 0 is done, so start advances to 1.

┌────┬────┬────┬────┐
│░ 7░│ 42 │ 25 │ 10 │
└────┴────┴────┴────┘
        ↑
    start = 1

The second pass scans positions 1 through 3, which hold 42, 25, and 10. The smallest is 10, and it swaps with 42 in position 1. Now start advances to 2.

┌────┬────┬────┬────┐
│░ 7░│░10░│ 25 │ 42 │
└────┴────┴────┴────┘
             ↑
         start = 2

The third pass scans positions 2 and 3, which hold 25 and 42. The smallest is 25, and it is already in position 2, so the swap exchanges it with itself and nothing moves. start advances to 3.

┌────┬────┬────┬────┐
│░ 7░│░10░│░25░│ 42 │
└────┴────┴────┴────┘
                  ↑
              start = 3

That leaves 42 alone in position 3, where start now points, and we stop. There is no fourth pass. When only one element is left unsorted, it is the largest of the whole array by elimination, and it is already in the only position left, so a pass over it could not change anything. This is why the outer loop below runs to size - 1 and not to size.

We are not going to make sort a method on DynamicArray. That is a design choice, and we will discuss it shortly. For now we put it in a separate utility class called ArrayUtils:

public class ArrayUtils {

  public static void selectionSort(DynamicArray list) {
    for (int i = 0; i < list.size() - 1; i++) {
      int minIndex = i;
      for (int j = i + 1; j < list.size(); j++) {
        if (list.get(j) < list.get(minIndex)) {
          minIndex = j;  // found a smaller element
        }
      }
      // swap the smallest remaining element into position i
      int temp = list.get(i);
      list.set(i, list.get(minIndex));
      list.set(minIndex, temp);
    }
  }
}

Read the inner loop carefully, because it is where the “find the smallest” step happens. minIndex starts at i, the first unsorted position, so we begin by assuming that element is the smallest. Then j scans the rest of the unsorted part, and every time list.get(j) is smaller than list.get(minIndex), minIndex moves to j. When the loop ends, minIndex is the index of the smallest element from i onward. The three lines after it swap that element with the one at i.

We call the sort without ever creating an ArrayUtils object:

ArrayUtils.selectionSort(numbers);

Notice that selectionSort uses only the array’s public operations: size, get, and set. It never accesses the private arr or size fields.

The cost of selection sort

contains has a best case. If the target is first, we stop after one comparison. Selection sort has no best case like that. To place each element, the inner loop has to scan every remaining element, because it cannot know it has found the smallest until it has looked at all of them. It does that whether the array is already sorted, reversed, or shuffled.

The swaps are a different story. When the smallest remaining element is already in position i, the swap exchanges the element with itself and nothing moves. We could skip that swap entirely by checking whether minIndex is still i. In the best case, the array is already sorted: every pass finds the smallest remaining element already in place, and no swap is needed. In the worst case, the array is reverse sorted, and most passes have to move an element into place. The scanning work is the same either way; only the swapping varies.