License Public Domain
Lines 33
Keywords
BogoSort (3)
Implements this Algorithm
Permissions
Owner: Stou S.
Viewable by Everyone
Editable by All Siafoo Users
Hide
Don't get spied on – We respect your privacy and provide numerous options to protect it. Join Siafoo Now or Learn More

Simple BogoSort implementation Atom Feed 0

In Brief An implementation of the sweet BogoSort algorithm. Just download, run, and enjoy.... more
# 's
 1from datetime import timedelta
2from random import shuffle
3from time import time
4
5def check_sort(ar):
6 for i in range(len(ar) - 1):
7 if ar[i] > ar[i + 1]:
8 return False
9
10 return True
11
12def bogo_sort(ar):
13
14 is_sorted = False
15 while not is_sorted:
16 is_sorted = check_sort(ar)
17
18 if is_sorted:
19 return ar
20
21 # Note that for even rather small len(ar), the total number of permutations of ar
22 # is larger than the period of most random number generators; this implies that
23 # most permutations of a long sequence can never be generated [from the Python Docs]
24 # What this means is that the algorithm may get stuck after a given array length
25 shuffle(ar)
26
27 return ar
28
29if __name__ == '__main__':
30
31 start = time()
32 print 'Sorting 1,2,3 ->', bogo_sort([1,2,3]), timedelta(seconds = time() - start)
33
34 start = time()
35 print 'Sorting 3,2,1 ->', bogo_sort([3,2,1]), timedelta(seconds = time() - start)
36
37 start = time()
38 print 'Sorting 3,4,5,6,7,1 ->', bogo_sort([3,4,5,6,7,1]), timedelta(seconds = time() - start)
39

An implementation of the sweet BogoSort algorithm. Just download, run, and enjoy.

Note that for even small len(ar), the total number of permutations of ar is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated [from the Python Docs] As such the algorithm may get stuck after a certain len(ar)

A sample run:

[stou@cipher src]$ python BogoSort.py
Sorting 1,2,3 -> [1, 2, 3] 0:00:00.000145
Sorting 3,2,1 -> [1, 2, 3] 0:00:00.000126
Sorting 3,4,5,6,7,1,10,11,41,456,89 -> [1, 3, 4, 5, 6, 7, 10, 11, 41, 89, 456] 0:05:46.684337

Comments

over 8 years ago (31 Jul 2008 at 02:35 PM) by Theodore Test
Say, this looks familiar. :)
over 8 years ago (04 Aug 2008 at 03:46 AM) by David Isaacson
You should do another one with a randomizer with C bindings (say something in NumPy)... I'm curious how fast it is.
over 8 years ago (04 Aug 2008 at 12:49 PM) by Theodore Test
`Working on it! <http://www.siafoo.net/snippet/160>`_ :D
over 8 years ago (04 Aug 2008 at 02:10 PM) by Stou S.
oh man you really are going to make us implement reST in comments... aren't you?
over 8 years ago (04 Aug 2008 at 02:26 PM) by Theodore Test
Sorry about that. :P

In the meantime, should I just stick with HTML tags, or raw-link things?
over 8 years ago (04 Aug 2008 at 05:02 PM) by Stou S.
Currently the comments only support text, but URLs are linkified... like: http://www.siafoo.net
over 8 years ago (04 Aug 2008 at 05:03 PM) by Stou S.
One problem with the comments supporting reST is that instead of 'editing' an object people will just post their version of the code in the comments... which reduces the usefulness of snippets.
over 8 years ago (04 Aug 2008 at 06:58 PM) by Theodore Test
How about using the built-in lexers to identify when someone tries to put code in a comment? At that point the system could toss out a warning/suggestion/redirection towards the editing/revision system...
over 8 years ago (04 Aug 2008 at 07:25 PM) by Stou S.
That's a good idea, disabling code blocks with a message to put it in the description or source of the object would probably be the best option. If someone comes up with a 'need' for code in comments we can re-enable it.
over 8 years ago (04 Aug 2008 at 07:44 PM) by Theodore Test
Disabling code blocks is definitely the most elegant approach. On the other hand, it won't catch when people omit the code-block syntax.
over 8 years ago (04 Aug 2008 at 07:44 PM) by Theodore Test
Back on the first hand, parsing comments through every lexer to snag lurking code is probably system-resource abuse. I think I've just devil's advocated my idea to hell. :)