[seqfan] Re: Slowest sort

[Max Alekseyev]

One more sorting algorithm with exponential running time -- sorting by
insertions of leading elements, see
http://dx.doi.org/10.1016/0097-3165(87)90022-7

Max
On Sep 13, 2013 2:42 PM, "Charles Greathouse" <charles.greathouse at case.edu>
wrote:

> I assume that things like delay loops aren't allowed.
>
> A good starting point would be the bogosort, where you reshuffle all
> elements unless they're already in order. This takes average time O(n*n!)
> with Fisher-Yates shuffling. To improve on this, the shuffle method must be
> made less favorable than random, or else the decision to shuffle must be
> made less often. The latter seems like cheating, though it could be
> concealed -- for example, clone the deck, shuffle both, then check if
> they're both in order for time O(n*n!^2) on average.
>
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University
>
>
> On Fri, Sep 13, 2013 at 12:10 PM, Ron Hardin <rhhardin at att.net> wrote:
>
> > Only semi-related, there was a contest at work once to come up with the
> > slowest sort algorithm.
> >
> > I don't remember what won.
> >
> >
> > rhhardin at mindspring.com
> > rhhardin at att.net (either)
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>