Difference between revisions of "Bogosort"

From CodeCodex

(Python: add ruby)
(Ruby: fix)
Line 221: Line 221:
 
     return lines
 
     return lines
 
</HIGHLIGHTSYNTAX>
 
</HIGHLIGHTSYNTAX>
==Ruby==
+
===Ruby===
 
<HIGHLIGHTSYNTAX language="ruby">  
 
<HIGHLIGHTSYNTAX language="ruby">  
 
def sorted?(lst)
 
def sorted?(lst)

Revision as of 05:27, 26 December 2009

Related content:

Implementations

BCPL

// This implementation does not do a full permutation between
// each comparison phase--it merely swaps two random elements.
// This does not change expected running time.

GET "LIBHDR"

LET SORTED(LIST, SIZE) =
VALOF $(
    LET I

    FOR I = 0 TO SIZE-2 DO
        IF LIST!I > LIST!(I+1) THEN RESULTIS 0

    RESULTIS 1
$)

// LIST = pointer to integer array, SIZE = size of array
LET BOGOSORT(LIST, SIZE) BE
$(
    LET I, J, T

    UNTIL (SORTED(LIST, SIZE)) DO
    $(
        I, J := RANDNO() REM SIZE, RANDNO() REM SIZE
        T, LIST!I, LIST!J = LIST!I, LIST!J, T
    $)
$)

C

<HIGHLIGHTSYNTAX language="c">

#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);
}

</HIGHLIGHTSYNTAX>

C++

<HIGHLIGHTSYNTAX language="cpp">

#include <algorithm>
#include <vector>

template<class T>
void bogosort(std::vector<T>& array)
{
    while (! is_sorted(array))
    {
         std::random_shuffle(array.begin(), array.end());
    }
}

template<class T>
bool is_sorted(const std::vector<T>& array)
{
    for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
    {
         if (array[i] < array[i-1])
         {
              return false;
         }
    }
    return true;
}

</HIGHLIGHTSYNTAX>

Java

<HIGHLIGHTSYNTAX language="java122"> //Sorts an integer array in ascending order. //Notice that the array passed must not be a null reference.

//Parameters: // data - the integer array to sort

//Postcondition: // The array is sorted in ascending order.

//Warning: // Due to the finite number of random sequences used by // java.util.Random it is possible that the execution // of this code will result in an infinite loop.

import java.util.Random;

public class BogoSort {

   private static final Random generator = new Random();
   public static void bogoSort(int[] data)
   {
       while (!isSorted(data)) {
           for (int i = 0; i < data.length; i++){
               int randomPosition = generator.nextInt(data.length);
               int temp = data[i];
               data[i] = data[randomPosition];
               data[randomPosition] = temp;
           }
       }
   }
   private static boolean isSorted(int[] data)
   {
       for (int i = 1; i < data.length; i++)
           if (data[i] < data[i - 1])
               return false;
       return true;
   }

} </HIGHLIGHTSYNTAX>

Perl

<HIGHLIGHTSYNTAX language="perl">

use List::Util 'shuffle';    # perldoc -q shuffle

sub is_sorted {
    for (1 .. $#_) {
        return if $_[$_ - 1] > $_[$_];
    };
    return 1;
};

sub bogosort {
    until (is_sorted @_) {
        @_ = shuffle @_;
    };
    return @_;
};

print bogosort qw(2 1 3);

</HIGHLIGHTSYNTAX>

PHP

<HIGHLIGHTSYNTAX language="php3"> function issorted($list) { for($j = 0; $j < $count; $j++) { for($k = $j + 1; $k < $count; $k++) { if(!($list[$j] < $list[$k])) return false; } } return true; } function bogosort($list) { do { shuffle($list); } while(!issorted($list)); return $list; } </HIGHLIGHTSYNTAX>

Python

<HIGHLIGHTSYNTAX language="python"> from random import shuffle from itertools import izip

def step(it):

   it.next()
   return it

def adjacents(seq):

   return izip(iter(seq), step(iter(seq)))

def is_sorted(seq):

   return len(seq) < 2 or all(a <= b for a, b in adjacents(seq))

def bogosort(lines):

   while not is_sorted(lines):
       shuffle(lines)
   return lines

</HIGHLIGHTSYNTAX>

Ruby

<HIGHLIGHTSYNTAX language="ruby"> def sorted?(lst)

 lst.zip(lst.slice(1..-1)).slice(0...-1).map{|p|p[0]<p[1]}.all?

end def bogosort(lst)

 while not sorted?(lst)
     lst.shuffle!
 end
 lst

end </HIGHLIGHTSYNTAX>