Software Physics

So the first algorithm that we’re going to work on is insertion sort. This is a very simple/intuitive routine, the easiest way to think about how it works is to consider how you might sort a handful of cards.

Starting with the cards to be sorted in your right (unsorted) hand, select a card and move it to your left (sorted) hand. Next, select another card from the unsorted hand and insert that card before (if it is less than) or after (if it is greater than) the card in your sorted hand. Repeat this process, inserting cards from the unsorted hand before the first card encountered in the sorted hand that the selected card is less than (or at the end if no such card is found).

Consider the following hand (let’s assume all the same suit)

Initial: Unsorted (6 2 7 8 J 9), Sorted ()

Round 1: Unsorted (2 7 8 J 9), Sorted (6)

Round 2: Unsorted (7 8 J 9), Sorted (2 6)

Round 3: Unsorted (8 J 9), Sorted (2 6 7)

Round 4: Unsorted (J 9), Sorted (2 6 7 8 )

Round 5: Unsorted (9), Sorted (2 6 7 8 J)

Round 6: Unsorted (), Sorted (2 6 7 8 9 J)

Here is some lisp code that implements the algorithm.

(defun insertion-sort (unsorted)
  (loop
     with sorted = ()
     for newitem in unsorted
     do (setf sorted (insert-item sorted newitem))
     finally (return sorted)))

(defun insert-item (x item)
  (cond
    ((not x) (cons item x))
    ((< item (first x)) (cons item x))
    (t (cons (first x) (insert-item (rest x) item)))))

[Note: I decided not to collapse the (not x) predicate with the (< item (first x)) predicate, which both have the same action form, for the sake clearly distinguishing between handling empty lists and non-empty ones]

Now, finally, let’s consider the performance of the algorithm.

On each round (loop iteration), the algorithm runs the insert-item routine so the worst case running time of the algorithm is equal to the sum of the worst case running times of insert-item on each invocation. The worst case running time of the insert-item routine, on a given round, equals the length of the sorted list at that round so, for instance, the worst case running time for the insert-item routine is 4 on the fourth round. The running time can, therefore, be expressed as:

∑_k=1..n k

Where n is the length of the list to be sorted. This is an arithmetic series and has the value:

1/2 (n)(n+1)

which is O(n²).

So there you have it. First baby-step along the way. It’s actually been harder than I expected to write up the algorithm summary. I realize everyone pretty much knows this stuff but the exercise of trying to explain it is pretty interesting. Not sure how well I’ll do as the algorithms and explanations get more complex but we’ll see!