Where Algorithms Live

We just wrote selectionSort as a static method in a separate ArrayUtils class, rather than as a method on DynamicArray like add and contains. Why did we put it there and not on the collection itself?

Compare it to other methods of DynamicArray. For example, contains is a question about a particular collection: does this collection hold this value? It cannot be answered without that collection, and the answer is different for every collection. So it belongs to the object.

Sorting is not like that. Sorting is a general-purpose procedure. The steps are the same for a dynamic array, a plain array, or any other 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. Java does the same thing. Java’s ArrayList, for example, has no sort method. Instead, there is a separate Collections class with a sort method. The sort method is a utility that can be used with any collection. Likewise, there is an Arrays class in Java that contains several static methods for working with arrays, including sort.

A class as a namespace

Putting selectionSort in ArrayUtils uses a class for a different job than DynamicArray does.

DynamicArray is a blueprint. We make objects from it, and each object has its own state. ArrayUtils is never instantiated. It holds no data, and there is no reason to construct one. It is a namespace: a name we group related static methods under.

Both are ordinary uses of a class. One bundles state together with the behavior that acts on it, and we make objects from it. The other groups a set of stand-alone operations, and we call it a utility class.

Since ArrayUtils is only ever meant to work as a namespace, we can make that intent explicit in the code:

public final class ArrayUtils {

  private ArrayUtils() {
    // This class is a namespace, not a blueprint. Do not instantiate it.
  }

  public static void selectionSort(DynamicArray list) { ... }
  // ... other static methods ...
}

Marking the class final means no one can extend it. A private constructor means no one outside the class can write new ArrayUtils(), because the constructor is not visible to them. Neither of these is needed for the code to run. What they do is make the compiler enforce that the class is only a namespace.