Why aren't we all speaking LISP now?

[Alex Martelli]

"Roy Smith" <roy at panix.com> wrote in message
news:roy-C59972.07100611052001 at news1.panix.com...
> "Delaney, Timothy" <tdelaney at avaya.com> wrote:
> > Indeed, the point of teaching bubblesort is to teach *not to use*
> > bubblesort. In general, teaching sorting algorithms is for learning
about
> > algorithms and why a good algorithm is so important.
>
> I've taught bubble sort as an introduction to algorithms.  Even though
it's
> generally considered to be a bad sorting algorithm, it's a very simple one
> and easy for students to grasp, and sorting is something that they're
    [snip]
Might you please explain what makes you choose it over _selection_ sort?

That would appear to me to share all the pluses you list for bubble in a
didactical role, but even more so -- e.g., what could be easier to grasp
than selection-sort's first-level top-down decomposition:

    def inplace_selection_sort(alist):
        L = len(alist)
        for i in range(L):
            # locate index of minimum in alist[i:L]
            j = find_smallest_in_sublist(alist, i, L)
            # swap, if need be, so alist[i] is the min
            swap_inside_list(alist, i, j)

Then one proceeds by giving a couple of further decompositions
of the find-smallest and swap-inside steps, to show how one
can use different ways to implement the same specs:

    def find_smallest_in_sublist(alist, from, onto):
        smallest_index = from
        for i in range(from+1, onto):
            if alist[i] < alist[smallest_index]:
                smallest_index = i
        return smallest_index

and

    def find_smallest_in_sublist(alist, from, onto):
        smallest_value = min(alist[from:onto])
        smallest_offset = alist[from:onto].index(smallest_value)
        return smallest_offset + from

etc, as well as

    def swap_inside_list(alist, i, j):
        alist[i],alist[j] = alist[j],alist[i]

and

    def swap_inside_list(alist, i, j):
        temp = alist[i]
        alist[i] = alist[j]
        alist[j] = temp

and the versions guarding these same bodies with an
"if i!=j:", etc, etc.

One can do both theoretical AND practical analysis of
performance characteristics of each version obtained
by either function-call or inline-substitution of the
various possible refinement-step implementations,
what if any advantages are gained by noticing the
toplevel loop need only go to range(L-1), etc.  The
presentation and study of selection sort would seem
to be an excellent step along the study of fundamental
algorithms.  What advantages does bubble offer over
selection...?


I've heard it claimed that 'bubble' is a more natural
way to sort.  I just can't get it.  As a bridge player,
I find myself in an environment where people are very
often sorting small sets (bridge hands they were just
dealt) compared with everyday life, and when kibitzing
other players I have the opportunity to observe how they
set about it.  It seems to be, for most people, first
a pass of bucket sort (more or less), separating cards
by suit, then on each suit roughly a selection sort --
each card is generally moved only once (typical of a
selection sort over a linked list, where putting the
new found subsequence-minimum to the right place only
requires "moving" it, not also moving another item as
in a typical item-swap for an array), roughly to its
final resting place.  I've NEVER seen the sequences of
small card-position moves (repeated swap of an item
with its adjacent one) typical of bubblesort...

...makes intuitive sense to me, too: in the real world,
examining items to see (e.g.) what is the smallest one
left to process only requires moving your eyes over the
items -- pretty fast and inexpensive -- while swapping
items is generally a physical move of real-world objects,
more slow and expensive.  So why shouldn't our brains
have evolved to naturally select-sort -- many inspections
(but -- each cheap), but minimal movement of 'data' (each
not-so-cheap, or very-expensive, being physical things)?


Alex