Why aren't we all speaking LISP now?

[Tim Peters]

[Danyel Fisher, on bubblesort]
> ...
> Also, it works as a naive recursive definition of sort in a world
> of lists:
>    A list is sorted if the elements one and two are in the correct
>    order, and elements numbered 2 through n are sorted.
>
> An intuitive "fix"--which implements the bubble sort--is:
> def sort(list):
>   if list[0] < list[1]:
>     return list[0] + sort( list[1:] )

And if the input is, e.g., [2, 3, 1]?  The first two elements are "in order",
so this returns 2 + sort([3, 1]), which blows up, but probably would return
[2, 1, 3] if it didn't <wink>.

>  else:
>    list[0], list[1] = list[1],list[0]
>    return sort( list[0]+sort(list[1:]))
>
> And, yes, that double recursive call in the second half is
> necessary, and it pretty much makes it clear WHY bubble sort isn't
> as cool as other sorts.  Admittedly, this doesn't have ANY
> optimizations, and it rather should. Any ideas of how to fix?

Would be better to make it work first.  A more natural way to approach an
algorithm from the given defn. is to focus on the second clause first; e.g.,

def bubble(x):
    if len(x) < 2:
        return x
    hd, tl = x[0], bubble(x[1:])
    # Now we can rely on "elements numbered 2 through n are sorted",
    # and deal w/ the first clause.
    if hd <= tl[0]:
        return [hd] + tl
    else:
        return bubble([tl[0], hd] + tl[1:])

This gives us a working sort, but despite the name "bubble" it's an
especially slow and clumsy variant of an insertion sort:

def insertionsort(x):
    if len(x) < 2:
        return x
    hd, tl = x[0], insertionsort(x[1:])
    return insert(hd, tl)

def insert(elt, x):
    if len(x) == 0:
        return [elt]
    hd, tl = x[0], x[1:]
    if elt <= hd:
        return [elt] + x
    else:
        return [hd] + insert(elt, tl)

Recursion can be a great way to obscure simple things <0.9 wink>.

fear-of-loops-isn't-a-virtue-in-real-life-ly y'rs  - tim