Bogosort (was: old threaded languages, was Re: Symbolics)

From: Aaron Christopher Finney <af-list_at_wfi-inc.com>
Date: Thu Mar 2 00:04:58 2000

> The only other in-place sort that seems more obvious to me is:

Which is the sort that probably 90% of CS101 students come up with before
they know what a sort is...

> which has the disadvantage over bubble sort of doing more swaps.
>
> A Shell-Metzner (sp?) sort is substantially more efficient but also much
> less obvious.

Ah, and no one has mentioned a heap sort yet (aka sift sort, or Williams
sort), which has the advantage of predictability (always NlogN) and no
such thing as a worst-case scenario, where as quicksort and shell sort
both have the capability of being N*N.


Aaron
Received on Thu Mar 02 2000 - 00:04:58 GMT