Why aren't we all speaking LISP now?
danyelf at ics.uci.edu
Sat May 12 04:11:48 CEST 2001
> You can always write an insertion sort and get it right. You can always
> write a bubble sort and get it right. The code is very similar in length.
> Conceptually, an insertion sort is more logical (despite this, *everyone*
> I've known, including myself, wrote a bubble sort as their first ever
> I wonder why?).
In my case, because after we wrote the algorithm, we stood up in the
classroom and buble sorted ourselves by age. It was very easy to simply
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:
if list < list:
return list + sort( list[1:] )
list, list = list,list
return sort( list+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?
More information about the Python-list