Selection Sort with Helper Methods

One of the important ideas in computer science is to break down complex problems into smaller, more manageable pieces. This is called decomposition. When we decompose a problem, we create smaller subproblems that are easier to solve and understand.

We have not seen an example of a complex algorithm to demonstrate this concept. Still, we can apply the idea to selection sort as an example. In selectionSort, each pass does two things. It finds the smallest remaining element, and then it moves that element into place. In the code those two things sit mixed together in one method. Let’s pull them apart.

Finding the smallest is a search. We scan the elements and keep track of the index of the smallest one we have seen so far. What changes from pass to pass is where the scan begins, since each pass only looks at the unsorted part. So we let the caller say where to start. That is the from argument, and on the first pass it is 0.

// Returns the index of the smallest element from index `from` to the end
public static int indexOfMin(DynamicArray list, int from) {
  int minIndex = from;
  for (int i = from + 1; i < list.size(); i++) {
    if (list.get(i) < list.get(minIndex)) {
      minIndex = i;
    }
  }
  return minIndex;
}

Moving an element into place means exchanging two positions:

public static void swap(DynamicArray list, int i, int j) {
  int temp = list.get(i);
  list.set(i, list.get(j));
  list.set(j, temp);
}

The temp variable is there because the first set overwrites position i. Without saving the old value first, we would lose it and end up with the same value in both positions.

Put the two together and you get one pass of selection sort. Do it in a loop over the elements and you get the full sort:

public static void selectionSort(DynamicArray list) {
  for (int i = 0; i < list.size() - 1; i++) {
    int min = indexOfMin(list, i);  // find the smallest remaining element
    swap(list, i, min);             // move it into position i
  }
}

The loop now reads as “for each position, find the smallest remaining element and swap it into place”, which is how we described selection sort in words before we wrote any code. The algorithm has not changed. The same comparisons happen in the same order, and the sorted prefix still grows one slot per pass. The only difference is that the two jobs are extracted into separate helper methods.

selectionSort is now an algorithm built out of two smaller algorithms. That is common. We build big procedures out of smaller ones, and each smaller one solves a piece of the problem. The code is easier to read that way. We also end up with pieces we can reuse elsewhere and pieces we can reason about independently. When we ask later how many comparisons selection sort does, indexOfMin is where all of them happen, and that is easier to see now than it was in the single block.