srlm@ukc.UUCP (S.R.L.Meira) (06/29/84)
[-: kipple :-] >From: ags@pucc-i (Seaman) >Newsgroups: net.sources >Subject: Re: Bubble sorts and such-like > >"...... > ...... >" >> I just like the clean and simple implementation it allows and it is easy to >> explain to people in a couple of minutes. > >Insertion sort is cleaner and simpler and easier to explain, besides being >faster. If you don't believe it, write down the loop invariants for the >two algorithms and see which one is simpler. You might also compare the >diagrams which Knuth used to illustrate the two sorts and see which is >simpler. > >"The teaching of bubble sorts ought to be considered a criminal offense." >-- > >Dave Seaman "My hovercraft is full of eels." >..!pur-ee!pucc-i:ags > Now come on and have a look at these two function (obvious names) and think again. Part of this discussion has been highly polarized because most people are looking at imperative languages ONLY. What follows is REAL krc - kent recursive calculator - and it has the same order of complexity of the imperative "implementations" of the same functions. [ note :- this is a krc comment, terminated by the next semi-colon. : is cons, (a:x) is a pattern standing for a list with head a and tail x, [] is the empty list, the equation general form is rhs = lhs , conditional. there we go ; insert a [] = [a] insert a (b:x) = a:b:x , a <= b = b : insert a x insertion_sort [] = [] insertion_sort (a:x) = insert a (insertion_sort x) now :- we define bubble_sort in terms of two functions: iterate, which is a fix-point operator and swap which is quite obvious ; iterate function argument = argument , argument = function (argument) = iterate function (function argument) swap [] = [] swap [a] = [a] swap (a:b:x) = a : swap (b:x) , a <= b = b : swap (a:x) and :- finally ; bubble_sort = iterate swap that :- is it ; ] I think THIS bubble sort is not more difficult to understand or prove than insertion sort. Performance is a bit worse, of course. It can be improved but that involves a more detailed krc description. Perhaps next time... silvio lemos meira UUCP: ...!{vax135,mcvax}!ukc!srlm Post: computing laboratory university of kent at canterbury canterbury ct2 7nf uk Phone: +44 227 66822 extension 568