This post covers the algorithm from Chapter 2, selection sort.

Imagine you have a row of numbered billiard balls, arranged in a random order and you want to sort them in order from smallest to largest.

You start by picking up the first ball and then move down the line, comparing each of the balls in the row to the one in your hand. As soon as you find one with a number smaller than the one you’re holding, you put down the ball in your hand and pick up the smaller number. You continue this until you’ve checked all the balls in the row, and put the smallest ball you found in a new, sorted row.

You then start over in the unsorted row until you find the smallest value from the remaining balls and add it to the end of the sorted row.

You repeat this until you’ve removed all of the balls from the unsorted row and placed them into the sorted row. The sorted row contains the billiard balls sorted by their numbers from smallest to largest.

Selection Sort

Now let’s implement the selection sort algorithm.

(defn selection-sort
  [arr]
  (loop [unsorted-arr arr
         sorted-arr   []]
    ))

We start by defining a function called selection-sort that takes in a single argument, arr. We also defined a loop with two values:

• unsorted-arr, to keep track of the remaining items from arr.
• sorted-arr, to keep track of the sorted values we pull out of arr.

Now, let’s add a condition to determine when to stop iterating.

(defn selection-sort
  [arr]
  (loop [unsorted-arr arr
         sorted-arr   []]
    (if-not (empty? unsorted-arr)
      ;(recur unsorted-arr-without-smallest sorted-arr-with-smallest)
      sorted-arr)))

The if-not form we added will iterate again as long as there are items left in unsorted-arr. If unsorted-arr is empty, we’ll return sorted-arr.

The recur comment we added above is just a placeholder, which allows us to see the shape of code from a high level without getting into the nitty gritty. This is what top-down design is all about.

Let’s implement our recur call now.

(defn selection-sort
  [arr]
  (loop [unsorted-arr arr
         sorted-arr   []]
    (if-not (empty? unsorted-arr)
      (let [smallest-index (find-smallest unsorted-arr)
            smallest       (get unsorted-arr smallest-index)]
        (recur (without-item unsorted-arr smallest-index)
               (conj sorted-arr smallest)))
      sorted-arr)))

We added a let with two variables defined. smallest-index is the index of the smallest value out of the remaining items. We use this in the next step to get the actual value of the smallest item remaining in unsorted-arr. Finally, we recur with the smallest item removed from unsorted-arr and appended to sorted-arr.

Our implementation of the selection-sort function is complete, but we referenced two functions we haven’t yet defined: find-smallest and without-item. Let’s define them now.

(defn- find-smallest
  [arr]
  (loop [i              0
         smallest-index 0]))

We defined the find-smallest function with a loop that keeps track of the current index with i and the index of the current smallest value with smallest-index.

(defn- find-smallest
  [arr]
  (loop [i              0
         smallest-index 0]
    (let [smallest (get arr smallest-index)]
      (cond
        (>= i (count arr))       smallest-index
        (< (get arr i) smallest) (recur (inc i) i)
        :else                    (recur (inc i) smallest-index)))))

We added a let where we define the smallest value we currently have. We also added a cond to branch on three conditions:

• We searched all the items in arr, return smallest-index.
• The current item is smaller than smallest, recur with i set to the next index and smallest-index set to i.
• Otherwise, recur with i set to the next index and smallest-index unchanged.

Let’s now define without-item.

(defn- without-item
  [arr index]
  {:pre [(< -1 index (count arr))]}
  (-> (concat (subvec arr 0 index)
              (subvec arr (inc index) (count arr)))
      vec))

without-item takes an array arr and returns an array with the item at index removed. It uses a precondition that requires that index is in bounds of arr.

The logic of our function breaks arr into two pieces: items before index and items after index. We concatenate those two halves and convert the resulting list to a vector.

Conclusion

Selection sort is an unsophisticated algorithm. It boils down to finding the smallest item in a list of n items, and repeating that n times.

Keep in mind is that much of the code we wrote is not useful in the real world. If you’re working as a software engineer and you need to find the smallest number in a list of numbers, you could just use (apply min unsorted-arr) instead of defining a find-smallest function like we wrote above.

Similarly, we could have just called (sort arr) instead of defining our selection-sort function altogether.

There are two times when you’re expected to write things from scratch: when you’re learning and when you’re demonstrating what you know.

Any other time, just use what already exists.