Rosetta Code

Sorting algorithms/Bogosort: Difference between revisions

Page Discussion

Sorting algorithms/Bogosort (view source)

Revision as of 11:48, 12 November 2014

44 bytes removed ,  9 years ago
m
{{out}}
m ({{out}})
Line 1:
{{task|Sorting Algorithms}}{{Sorting Algorithm}}
[[wp:Bogosort|Bogosort]] a list of numbers. Bogosort simply shuffles a collection randomly until it is sorted.
Bogosort simply shuffles a collection randomly until it is sorted.
 
"Bogosort" is a perversely inefficient algorithm only used as an in-joke.
"Bogosort" is a perversely inefficient algorithm only used as an in-joke. Its average run-time is O(n!) because the chance that any given shuffle of a set will end up in sorted order is about one in ''n'' factorial, and the worst case is infinite since there's no guarantee that a random shuffling will ever produce a sorted sequence. Its best case is O(n) since a single pass through the elements may suffice to order them.
 
Pseudocode:
Line 101 ⟶ 103:
end loop;
end Test_Bogosort;</lang>
The solution is generic.
The solution is generic. The procedure Bogosort can be instantiated with any copyable comparable type. In the example given it is the standard Integer type. Sample output:
The procedure Bogosort can be instantiated
with any copyable comparable type.
In the example given it is the standard Integer type.
{{out}}
<pre>
3 6 7 9
Line 151 ⟶ 157:
[6]TYPE sample := (61, 52, 63, 94, 46, 18);
print((bogo sort(sample), new line))</lang>
{{out}}
Output:
+18 +46 +52 +61 +63 +94
 
Line 248 ⟶ 254:
NEXT
= TRUE</lang>
{{out}}
'''Output:'''
<pre>
383150 shuffles required to sort 10 items.
Line 333 ⟶ 339:
std::cout << "\n";
}</lang>
{{out}}
Output:
<pre>
-199 -52 2 3 33 56 99 100 177 200
Line 443 ⟶ 449:
writeln(array);
}</lang>
{{out}}
Output:
<pre>[1, 2, 3, 5, 6, 7, 8, 11, 41]</pre>
 
Line 557 ⟶ 563:
end
</lang>
{{out}}
Output:
<pre>
Unsorted: 3 2 5 7 1
Line 597 ⟶ 603:
? bogosort(shuffle({1,2,3,4,5,6}))</lang>
 
{{out}}
Output:
<pre>{1,2,5,4,6,3}
{5,1,3,6,2,4}
Line 720 ⟶ 726:
fmt.Println("sorted! ", temp)
}</lang>
Output:{{out}} (sometimes takes a few seconds)
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
Line 740 ⟶ 746:
<lang groovy>println (bogosort([3,1,2]))</lang>
 
Output,{{out}} trial 1:
<pre>..............................[1, 2, 3]</pre>
 
Output,{{out}} trial 2:
<pre>...................................................[1, 2, 3]</pre>
 
Line 910 ⟶ 916:
</lang>
 
{{out}}
Output:
<pre>Unsorted: 4 5 6 0 7 8 9 1 2 3
This took 23104714 shuffles.
Line 1,049 ⟶ 1,055:
end</lang>
 
{{out}}
Sample Output:
<lang MATLAB>bogoSort([5 3 8 4 9 7 6 2 1])
 
Line 1,234 ⟶ 1,240:
return \isTrue
</lang>
{{out}}
;Output
<pre>
unsorted: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84]
Line 1,263 ⟶ 1,269:
bogoSort a
echo a</lang>
{{out}}
Output:
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
 
Line 1,463 ⟶ 1,469:
end.</lang>
 
{{out}}
Sample Output:
<pre>1: 5 4 3 2 1
2: 3 5 4 1 2
Line 1,516 ⟶ 1,522:
Lst )
(T (apply <= Lst) Lst) ) )</lang>
{{out}}
Output:
<pre>: (bogosort (make (do 9 (link (rand 1 999)))))
-> (1 167 183 282 524 556 638 891 902)
Line 1,592 ⟶ 1,598:
 
BogoSort(b())</lang>
{{out}}
Sample output:
<pre>Array of 10 integers required 2766901 shuffles To SORT.</pre>
 
Line 1,696 ⟶ 1,702:
</lang>
 
Output{{out}} (chances are you won't get quite this!):
<pre>
(703 931 12 713 894 232 778 86 700 26)
Line 1,734 ⟶ 1,740:
say
return</lang>
'''output'''{{out}} using the default input:
<pre>
───────────────un-bogoed────────────────
Line 1,796 ⟶ 1,802:
say
return</lang>
{{out}}
'''output'''
<pre style="height:30ex">
───────────────un-bogoed────────────────
Line 2,019 ⟶ 2,025:
end</lang>
 
{{out}}
Sample Output:
<pre>1: 5 4 3 2 1
2: 2 1 4 3 5
Line 2,142 ⟶ 2,148:
 
example = bogosort <8,50,0,12,47,51></lang>
{{out}}
output:
<pre><0,8,12,47,50,51></pre>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72251"