From Algorithm wiki
 Related content:
|
|
|
[edit] Pseudocode
This section needs your Code!
[edit] C Code
#include <stdlib.h>
#include <string.h>
int isSorted(char **lines)
{
/* Array contains 0 or 1 strings, it's guaranteed to be sorted. */
if ((*lines == NULL) || (*(lines + 1) == NULL))
return 1;
lines++;
for ( ; *lines; lines++)
{
if (strcmp(*lines, *(lines-1)) < 0)
return 0;
}
return 1; /* True if nothing fails. */
}
size_t arrLen(char **lines)
{
int i=0;
for ( ; *lines; lines++, i++) ;
return i;
}
void shuffle(char **lines)
{
size_t length = arrLen(lines);
size_t randN;
size_t i;
char *temp;
for (i = 0; i < length; i++)
{
randN = rand() % length;
temp = lines[i];
lines[i] = lines[randN];
lines[randN] = temp;
}
}
void bogosort(char **lines)
{
while (!isSorted(lines))
shuffle(lines);
}
[edit] C++ Code
// This makes use of STL
#include <algorithm>
using namespace std;
template<typename Iterator>
void bogosort(Iterator begin, Iterator end)
{
while(!is_sorted(begin, end))
random_shuffle(begin, end);
}
[edit] PHP Code
This section needs your Code!
[edit] C# Code
using System;
namespace Bogosort
{
class Program
{
private static System.Random rnd = new System.Random();
private static int compctr = 0;
static void Main(string[] args)
{
int[] array = GenRandomArray(6);
Console.WriteLine("Sorting a list of " + array.Length + " random numbers between 0 and " + 10 * array.Length + ".");
Console.Write("Original array: ");
PrintArray(array);
int i = 0;
System.DateTime startTime = System.DateTime.Now;
while (!Sorted(array))
{
array = Shuffle(array);
Console.Write("Shuffle " + i + ": ");
PrintArray(array);
i++;
}
System.DateTime stopTime = System.DateTime.Now;
Console.Write("The sorted array is: ");
PrintArray(array);
Console.WriteLine("This required " + i + " shufflings and took " + (stopTime-startTime).Milliseconds + " milliseconds.");
Console.WriteLine("The total number of comparisons made was " + compctr + ", which is " + (double)compctr / (double)i + " comparisons on average.");
Console.WriteLine("The total number of swaps made was " + array.Length * i + ".");
}
private static int Factorial(int x)
{
if (x < 2) return 1;
return x * Factorial(x - 1);
}
private static void PrintArray(int[] array)
{
string s = "";
for (int i =0; i<array.Length-1; i++)
{
s += array[i] + ", ";
}
Console.WriteLine(s + array[array.Length - 1]);
}
private static int[] GenRandomArray(int length)
{
int[] array = new int[length];
for (int i = 0; i < length; i++)
{
array[i] = rnd.Next(10*length);
}
return array;
}
private static bool Sorted(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
compctr++;
if (array[i] < array[i - 1]) return false;
}
return true;
}
private static int[] Shuffle(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int pos = rnd.Next(array.Length);
int temp = array[pos];
array[pos] = array[i];
array[i] = temp;
}
return array;
}
}
}
[edit] Java Code
import java.util.Random;
public class BogoSort
{
private static final int NUMBERS = 15;
private static final int MAX_VALUE = 1000;
private int[] numbers;
private Random rnd;
public BogoSort()
{
rnd = new Random();
numbers = new int[NUMBERS];
System.out.println("Generating random numbers...");
for(int i = 0; i < NUMBERS; i++)
{
numbers[i] = rnd.nextInt(MAX_VALUE);
System.out.print(numbers[i] + " ");
}
System.out.println("\n\nNumbers generated. Commencing random sorting...\n");
long startTime = System.currentTimeMillis();
while(!isSorted())
{
shuffle();
}
long totalTime = (System.currentTimeMillis() - startTime);
System.out.println("Sorting finished! Total sorting time: " + totalTime + " ms.");
for(int i = 0; i < NUMBERS; i++)
{
System.out.print(numbers[i] + " ");
}
}
private void shuffle()
{
for(int i = 0; i < NUMBERS; i++)
{
int rand = rnd.nextInt(NUMBERS);
int temp = numbers[i];
numbers[i] = numbers[rand];
numbers[rand] = temp;
}
}
private boolean isSorted()
{
for(int i = 0; i < NUMBERS-1; i++)
{
if((numbers[i] > numbers[i+1]))
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
new BogoSort();
}
}
[edit] VB Code
This section needs your Code!
[edit] Perl Code
#!/usr/bin/perl
use List::Util qw(shuffle);
# use: bogosort(@deck);
sub bogosort{
my @a = @_;
until (is_sorted(@a)) {
@a = shuffle(@a);
}
return @a;
}
# use: is_sorted(@deck);
sub is_sorted{
my @a = @_;
foreach my $i (0 .. $#a-1) {
if ($a[$i] > $a[$i+1]) {
return 0;
}
}
return 1;
}
#example
@a = (0, 6, 2, 4, 8, 6, 7, 1);
@sorted = bogosort(@a);
print @sorted, "\n";
[edit] Prolog Code
perm([H|T],L):-perm(T,TT),append(X1,X2,TT),append(X1,[H|X2],L).
perm([],[]).
sorted([]).
sorted([X]).
sorted([H1,H2|T]):-H1<H2,sorted([H2|T]).
sort(L,SL):-perm(L,SL),sorted(SL).
[edit] Python Code
import random
def already_sorted (array):
for i in xrange (len (array) - 1):
if array[i] > array[i+1]:
return False
return True
def bogosort (array):
while not already_sorted(array):
random.shuffle (array)
[edit] Ruby Code
def bogo_sort(array)
ary = array.dup
def ary.sorted?
for i in 0..self.size-2
return false if self[i] > self[i+1]
end
end
ary.replace(ary.sort_by{rand}) until ary.sorted?
ary
end
[edit] Bigloo Scheme Code
(define (foldl f acc l)
(if (eq? l '())
acc
(foldl f (f acc (car l)) (cdr l))))
(define (sorted? l)
(not (= -1
(foldl (lambda (acc x)
(cond
((= acc -1) -1)
((>= x acc) x)
(else -1))) 0 l))))
(define (bogosort l)
(let ((newl (sort (lambda (a b) (= 0 (random 2))) l)))
(if (sorted? newl)
newl
(bogosort l))))
Related content:
