This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

bogosort [2014/04/27 15:14] will |
bogosort [2015/02/02 08:28] (current) |
||
---|---|---|---|

Line 4: | Line 4: | ||

Bogosort takes on average $n!$ attempts to select the right answer. Since each ''isSorted'' and ''shuffle'' are $O(n)$, bogosort takes $O(n.n!)$ time overall. The extreme time complexity is the reason this example is only sorting 5 items. | Bogosort takes on average $n!$ attempts to select the right answer. Since each ''isSorted'' and ''shuffle'' are $O(n)$, bogosort takes $O(n.n!)$ time overall. The extreme time complexity is the reason this example is only sorting 5 items. | ||

+ | |||

+ | This implementation makes use of [[Is Sorted]] and [[Fisher-Yates shuffle]]. | ||

+ | |||

+ | ===== Properties ===== | ||

+ | * $O(1)$ space | ||

+ | * $O(n.n!)$ time | ||

+ | * Not stable | ||

+ | * Not adaptive | ||

[algorithm bogosort] | [algorithm bogosort] |

bogosort.1398636861.txt.gz ยท Last modified: 2015/02/02 08:24 (external edit)