Source code online books for professionals by professionals

Listing 4-1.  Recursive Insertion Sort
def ins_sort_rec(seq, i):
    if i==0: return                             # Base case -- do nothing
    ins_sort_rec(seq, i-1)                      # Sort 0..i-1
    j = i                                       # Start "walking" down
    while j > 0 and seq[j-1] > seq[j]:          # Look for OK spot
        seq[j-1], seq[j] = seq[j], seq[j-1]     # Keep moving seq[j] down
        j -= 1                                  # Decrement j
 
Listing 4-2 shows the iterative version more commonly known as insertion sort. Instead of recursing backward, 
it iterates forward, from the first element. If you think about it, that’s exactly what the recursive version does too. 
Although it seems to start at the end, the recursive calls go all the way back to the first element before the while loop 
is ever executed. After that recursive call returns, the while loop is executed on the second element, and so on, so the 
behaviors of the two versions are identical.
Listing 4-2.  Insertion Sort
def ins_sort(seq):
    for i in range(1,len(seq)):                 # 0..i-1 sorted so far
        j = i                                   # Start "walking" down
        while j > 0 and seq[j-1] > seq[j]:      # Look for OK spot
            seq[j-1], seq[j] = seq[j], seq[j-1] # Keep moving seq[j] down
            j -= 1                              # Decrement j
 
Listings 4-3 and 4-4 contain a recursive and an iterative version of selection sort, respectively.
7
These algorithms aren’t all that useful, but they’re commonly taught, because they serve as excellent examples. Also, they’re 
classics, so any algorist should know how they work.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
75
Listing 4-3.  Recursive Selection Sort
def sel_sort_rec(seq, i):
    if i==0: return                             # Base case -- do nothing
    max_j = i                                   # Idx. of largest value so far
    for j in range(i):                          # Look for a larger value
        if seq[j] > seq[max_j]: max_j = j       # Found one? Update max_j
    seq[i], seq[max_j] = seq[max_j], seq[i]     # Switch largest into place
    sel_sort_rec(seq, i-1)                      # Sort 0..i-1
Listing 4-4.  Selection Sort
def sel_sort(seq):
    for i in range(len(seq)-1,0,-1):            # n..i+1 sorted so far
        max_j = i                               # Idx. of largest value so far
        for j in range(i):                      # Look for a larger value
            if seq[j] > seq[max_j]: max_j = j   # Found one? Update max_j
        seq[i], seq[max_j] = seq[max_j], seq[i] # Switch largest into place
 
Once again, you can see that the two are quite similar. The recursive implementation explicitly represents the 
inductive hypothesis (as a recursive call), while the iterative version explicitly represents repeatedly performing  
the inductive step. Both work by finding the largest element (the for loop looking for max_j) and swapping that to the 
end of the sequence prefix under consideration. Note that you could just as well run all the four sorting algorithms in 
this section from the beginning, rather than from the end (sort all objects to the right in insertion sort or look for the 
smallest element in selection sort).