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

From: Carlos Murillo <cem14_at_cornell.edu>
Date: Wed Mar 1 19:48:13 2000

At 01:51 PM 03/01/2000 -0500, you wrote:
>
>1. Take the list of numbers you want to sort.
>2. Randomly reorganize them.
>3. Check to see if they're sorted. If not, go back to step 2.
>
>This is a Order(n*factorial(n)) algorithm. I've tried, but I've been
>unable to come up with anything worse.
>
>For your example of 1000 numbers, it'd take (assuming that each operation
>takes a microsecond) about 10^2554 years to complete.

Provided that you have a well-behaved rand() . Most implementations
aren't and a perfect sort might not be reachable :-)

Carlos.
Received on Wed Mar 01 2000 - 19:48:13 GMT