Building Up to Selection Sort

When we learned about DynamicArray we wrote ArrayUtils, a namespace of algorithms that operate on a DynamicArray. Three of them are built on one another:

swap(a, i, j) exchanges the elements at positions i and j.
indexOfMin(a, from) returns the index of the smallest element in the part of the array from from to the end.
selectionSort(a) sorts the array by repeatedly finding the smallest remaining element and moving it into place. It uses indexOfMin to find the smallest element in the unsorted tail, and swap to move it to the front of that tail.

Let’s find the Big-Oh of each, working up to selection sort. Let $n$ be the number of elements in the array. Here is a table of the operations and their Big-Oh:

Operation	Big-Oh
`swap`	$O (1)$
`indexOfMin`	$O (n)$
`selectionSort`	$O (n^{2})$

swap exchanges two elements at known positions. It is basically three reads and three writes:

int temp = a.get(i);
a.set(i, a.get(j));
a.set(j, temp);

Reading or writing the element at a known index does not depend on how many elements are in the array. So for any $n$ , swap does the same $6$ operations. Let’s apply our two-step procedure for determining Big-Oh. First, we suppress the coefficients, so $6$ becomes $1$ . Then we drop the lower-order terms, but there are none. The only term is $1$ , so we write $O (1)$ .

indexOfMin has to find the smallest element in the part of the array from from to the end, and the only way to do that is to look at every element in that part, keeping track of the smallest seen so far. So it examines at most $n$ elements, when from is $0$ , with a constant amount of work for each one. Constant work repeated $n$ times is $O (n)$ .

Let’s look at selectionSort now:

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

The loop runs $n$ times, and each time it calls indexOfMin and swap. The swap is $O (1)$ and the indexOfMin is $O (n)$ . So the body of the loop is $O (n) + O (1)$ , which is $O (n)$ . The loop runs $n$ times, and each time it does $O (n)$ work, so the total work is $O (n) \cdot O (n)$ , which is $O (n^{2})$ .

The point to take away is that when you work out the Big-Oh of a method, you have to work out the Big-Oh of the methods it calls too, and count how many times it calls them.