On Fri, 25 Jun 2010, Richard Fateman wrote:
< Leo Butler wrote:
< > On Fri, 25 Jun 2010, Jeffrey Hankins wrote:
< >
< > < Thanks. That was obviously the line I intended. If you're curious, I've
< > written a few interesting things. I even found a way to write quicksort and
< > merge sort in
< > < Maxima:
< >
< > You may wish to add your code to:
< >
< > http://www.codecodex.com/wiki/Merge_sort
< > http://www.codecodex.com/wiki/Quicksort
< >
< > http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort
< > http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
< >
< > Leo
< >
< Because of the way it is written, using endcons and append, it is not like
< quicksort, which is O(n log n).
< It is probably worse than O(n^4), whereas a normal naive sorting program is
< O(n^2).
<
<
< endcons takes time proportional to the length of the list, and is almost
< always a bad idea.
< Compare to cons, which takes constant time, and is very fast.
<
<
< I think that much better (clearer and shorter) programs could be written.
Indeed.
<
< There is also a "sort" program built in.
<
< Here is an outline of mergesort.
<
< mergesort(L)
< if (length(L)<=1) then L else merge
< (mergesort(leftpart(L)),mergesort(rightpart(L));
<
< you get the idea.
The devil (and cruft) is in the details.
I suggested putting Maxima code on these pages to expose Maxima --
advertising, if you will. Nice, compact, expressive code is a plus.
If you peruse the code already on those pages, you will see that
these qualities vary between languages and authors.
Leo
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.