Algorithms and Selection Sort

The questions on this page are about algorithms over a DynamicArray: a collection of int values that keeps its elements in the order they were added. The sorting questions use only its public interface:

public int size();                       // number of elements
public int get(int index);               // element at index; valid for 0 <= index < size()
public void set(int index, int value);   // overwrites the element at index; same validity

Utility code goes in a separate class:

public final class ArrayUtils {
  private ArrayUtils() { }
  // static methods go here.
}

Solution

An algorithm is a step-by-step procedure for solving a problem. The four properties:

The steps are unambiguous: each one is precise and can actually be carried out.
The steps happen in a definite order.
It is finite: it terminates after a finite number of steps.
It has well-defined input and output: a clear set of inputs and a result.

Exercise

Here is linear search over the dynamic array, written inside the class (arr is the private backing array, and size counts the elements):

public boolean contains(int value) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == value) {
      return true;
    }
  }
  return false;
}

Check it against the four properties to confirm it is an algorithm.

Solution

Each step is a comparison and an increment, so the steps are unambiguous. The loop fixes the order. It is finite because size is a finite number and i increases every pass, so the loop must end. The input is a value and a collection, and the output is true or false. All four hold, so linear search is an algorithm.

Exercise

Write two static helpers in ArrayUtils, using only the dynamic array’s public operations:

// Returns the index of the smallest element from index `from` to the end
public static int indexOfMin(DynamicArray list, int from) { ... }

// Exchanges the elements at indices i and j
public static void swap(DynamicArray list, int i, int j) { ... }

Solution

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;
}

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);
}

Solution

public static void selectionSort(DynamicArray list) {
  for (int i = 0; i < list.size() - 1; i++) {
    int min = indexOfMin(list, i);
    swap(list, i, min);
  }
}

When only one element is left unsorted, it is the largest of the whole array by elimination, and it already sits in the only position left, so a final pass could not change anything.

Solution

contains is a question about one particular collection, so it belongs to the object. Sorting is a general-purpose procedure: the steps are the same for any structure we can read and write by index, and knowing how to sort is not part of what it means to be a dynamic array.