Lines 33
BogoSort (3)
##### Permissions
Owner: Stou S.
Viewable by Everyone
Editable by All Siafoo Users
Stay up to dateembedded code automagically updates, each snippet and article has a feed

# Simple BogoSort implementation 0

 In Brief An implementation of the sweet BogoSort algorithm. Just download, run, and enjoy.... more
 Language Python
# '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

over 12 years ago (31 Jul 2008 at 02:35 PM) by Theodore Test
Say, this looks familiar. :)
over 12 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 12 years ago (04 Aug 2008 at 12:49 PM) by Theodore Test
`Working on it! <http://www.siafoo.net/snippet/160>`_ :D
over 12 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 12 years ago (04 Aug 2008 at 02:26 PM) by Theodore Test

In the meantime, should I just stick with HTML tags, or raw-link things?
over 12 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 12 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 12 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 12 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 12 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 12 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. :)