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. Because selectionSort is outside the class, it has no access to the private fields. It has to reach the elements through size, get, and set, like any other client.