Sorting algorithms/Bogosort: Difference between revisions
Content deleted Content added
No edit summary |
|||
Line 7: | Line 7: | ||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
<actionscript> |
<lang actionscript> |
||
public function bogoSort(arr:Array):Array |
public function bogoSort(arr:Array):Array |
||
{ |
{ |
||
Line 45: | Line 45: | ||
return true; |
return true; |
||
} |
} |
||
</lang> |
|||
</actionscript> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<ada> |
<lang ada> |
||
with Ada.Text_IO; use Ada.Text_IO; |
with Ada.Text_IO; use Ada.Text_IO; |
||
with Ada.Numerics.Discrete_Random; |
with Ada.Numerics.Discrete_Random; |
||
Line 99: | Line 99: | ||
end loop; |
end loop; |
||
end Test_Bogosort; |
end Test_Bogosort; |
||
</ |
</lang> |
||
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 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: |
||
<pre> |
<pre> |
||
Line 106: | Line 106: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. |
The following algorithm actually works for all sequences of comparable types; restricting to lists of integers would not make the code simpler. |
||
<cpp>#include <iterator> |
<lang cpp>#include <iterator> |
||
#include <algorithm> |
#include <algorithm> |
||
Line 117: | Line 117: | ||
while (std::adjacent_find(begin, end, std::greater<value_type>()) != end) |
while (std::adjacent_find(begin, end, std::greater<value_type>()) != end) |
||
std::random_shuffle(begin, end); |
std::random_shuffle(begin, end); |
||
}</ |
}</lang> |
||
Using the is_sorted function, part of the SGI STL implementation: |
Using the is_sorted function, part of the SGI STL implementation: |
||
{{works with|GCC}} |
{{works with|GCC}} |
||
<cpp>#include <algorithm> |
<lang cpp>#include <algorithm> |
||
#include <ext/algorithm> |
#include <ext/algorithm> |
||
Line 129: | Line 129: | ||
while (!__gnu_cxx::is_sorted(begin, end)) |
while (!__gnu_cxx::is_sorted(begin, end)) |
||
std::random_shuffle(begin, end); |
std::random_shuffle(begin, end); |
||
}</ |
}</lang> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{works with|C sharp|C#|3.0+}} |
{{works with|C sharp|C#|3.0+}} |
||
<csharp> |
<lang csharp> |
||
using System; |
using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 182: | Line 182: | ||
} |
} |
||
} |
} |
||
</ |
</lang> |
||
=={{header|D}}== |
=={{header|D}}== |
||
<d>module bogosort ; |
<lang d>module bogosort ; |
||
import std.stdio, std.random ; |
import std.stdio, std.random ; |
||
Line 209: | Line 209: | ||
writefln("%s", b) ; // sort is in place |
writefln("%s", b) ; // sort is in place |
||
}</ |
}</lang> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
Line 327: | Line 327: | ||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
This implementation works for all comparable types (types with <tt>compareTo</tt> defined). |
||
<java>import java.util.Collections; |
<lang java>import java.util.Collections; |
||
import java.util.List; |
import java.util.List; |
||
import java.util.Iterator; |
import java.util.Iterator; |
||
Line 350: | Line 350: | ||
Collections.shuffle(list); |
Collections.shuffle(list); |
||
} |
} |
||
}</ |
}</lang> |
||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
< |
<lang modula3>MODULE Bogo EXPORTS Main; |
||
IMPORT IO, Random; |
IMPORT IO, Random; |
||
Line 397: | Line 397: | ||
END; |
END; |
||
IO.PutChar('\n'); |
IO.PutChar('\n'); |
||
END Bogo.</ |
END Bogo.</lang> |
||
=={{header|Oberon-2}}== |
=={{header|Oberon-2}}== |
||
Line 457: | Line 457: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<ocaml> |
<lang ocaml> |
||
let rec is_sorted comp = function |
let rec is_sorted comp = function |
||
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r) |
| e1 :: e2 :: r -> comp e1 e2 <= 0 && is_sorted comp (e2 :: r) |
||
Line 478: | Line 478: | ||
else |
else |
||
bogosort (shuffle li) |
bogosort (shuffle li) |
||
</ |
</lang> |
||
Example: |
Example: |
||
<pre> |
<pre> |
||
Line 486: | Line 486: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<perl>sub bogosort |
<lang perl>sub bogosort |
||
{my @l = @_; |
{my @l = @_; |
||
shuffle(\@l) until in_order(@l); |
shuffle(\@l) until in_order(@l); |
||
Line 505: | Line 505: | ||
for (my $n = $#l ; $n ; --$n) |
for (my $n = $#l ; $n ; --$n) |
||
{my $k = int rand($n + 1); |
{my $k = int rand($n + 1); |
||
@l[$k, $n] = @l[$n, $k] if $k != $n;}}</ |
@l[$k, $n] = @l[$n, $k] if $k != $n;}}</lang> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
<php>function bogosort($l) { |
<lang php>function bogosort($l) { |
||
while (!in_order($l)) |
while (!in_order($l)) |
||
shuffle($l); |
shuffle($l); |
||
Line 519: | Line 519: | ||
return FALSE; |
return FALSE; |
||
return TRUE; |
return TRUE; |
||
}</ |
}</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
<python>import random |
<lang python>import random |
||
def bogosort(l): |
def bogosort(l): |
||
Line 537: | Line 537: | ||
return False |
return False |
||
last = x |
last = x |
||
return True</ |
return True</lang> |
||
Alternative definition for ''in_order'' (Python 2.5) |
Alternative definition for ''in_order'' (Python 2.5) |
||
<python>def in_order(l): |
<lang python>def in_order(l): |
||
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</ |
return all( l[i] <= l[i+1] for i in xrange(0,len(l)-1))</lang> |
||
An alternative implementation for Python 2.5 or later: |
An alternative implementation for Python 2.5 or later: |
||
<python>import random |
<lang python>import random |
||
def bogosort(lst): |
def bogosort(lst): |
||
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :) |
random.shuffle(lst) # must shuffle it first or it's a bug if lst was pre-sorted! :) |
||
while lst != sorted(lst): |
while lst != sorted(lst): |
||
random.shuffle(lst) |
random.shuffle(lst) |
||
return lst</ |
return lst</lang> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<ruby>def shuffle(l) |
<lang ruby>def shuffle(l) |
||
l.sort_by { rand } |
l.sort_by { rand } |
||
end |
end |
||
Line 564: | Line 564: | ||
def in_order(l) |
def in_order(l) |
||
(0..l.length-2).all? {|i| l[i] <= l[i+1] } |
(0..l.length-2).all? {|i| l[i] <= l[i+1] } |
||
end</ |
end</lang> |
||
An alternative implementation: |
An alternative implementation: |
||
<ruby>def shuffle(l) |
<lang ruby>def shuffle(l) |
||
l.sort_by { rand } |
l.sort_by { rand } |
||
end |
end |
||
Line 575: | Line 575: | ||
l = shuffle(l) until l == l.sort |
l = shuffle(l) until l == l.sort |
||
l |
l |
||
end</ |
end</lang> |