ソートアルゴリズム——サルソート(Bogosort)【コード実装】

ぎじふごう

while not InOrder(list) do
   Shuffle(list)
done

ActionScript

public function bogoSort(arr:Array):Array
{
    while (!sorted(arr))
    {
        shuffle(arr);
    }
 
    return arr;
}
 
public function shuffle(arr:Array):void
{
    for (var i:int = 0; i < arr.length; i++)
    {
        var rand:int = Math.floor(Math.random() * arr.length);
        var tmp:* = arr[i];
        arr[i] = arr[rand];
        arr[rand] = tmp;
    }
}
 
public function sorted(arr:Array):Boolean
{
    var last:int = arr[0];
 
    for (var i:int = 1; i < arr.length; i++)
    {
        if (arr[i] < last)
        {
            return false;
        }
 
        last = arr[i];
    }
 
    return true;
}

C

#include 
#include 
#include 
 
bool is_sorted(int *a, int n)
{
  while ( --n >= 1 ) {
    if ( a[n] < a[n-1] ) return false;
  }
  return true;
}
 
void shuffle(int *a, int n)
{
  int i, t, r;
  for(i=0; i < n; i++) {
    t = a[i];
    r = rand() % n;
    a[i] = a[r];
    a[r] = t;
  }
}
 
void bogosort(int *a, int n)
{
  while ( !is_sorted(a, n) ) shuffle(a, n);
}
 
int main()
{
  int numbers[] = { 1, 10, 9,  7, 3, 0 };
  int i;
 
  bogosort(numbers, 6);
  for (i=0; i < 6; i++) printf("%d ", numbers[i]);
  printf("
");
}

C++

#include 
#include 
#include 
#include 
 
template <typename RandomAccessIterator, typename Predicate>
void bogo_sort(RandomAccessIterator begin, RandomAccessIterator end,
               Predicate p) {
  std::random_device rd;
  std::mt19937 generator(rd());
  while (!std::is_sorted(begin, end, p)) {
    std::shuffle(begin, end, generator);
  }
}
 
template <typename RandomAccessIterator>
void bogo_sort(RandomAccessIterator begin, RandomAccessIterator end) {
  bogo_sort(
      begin, end,
      std::less<
          typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
 
int main() {
  int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
  bogo_sort(std::begin(a), std::end(a));
  copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "
";
}

C#

using System;
using System.Collections.Generic;
 
namespace RosettaCode.BogoSort
{
    public static class BogoSorter
    {
        public static void Sort<T>(List<T> list) where T:IComparable
        {
            while (!list.isSorted())
            {
                list.Shuffle();
            }
        }
 
        private static bool isSorted<T>(this IList<T> list) where T:IComparable
        {
            if(list.Count<=1)
                return true;
            for (int i = 1 ; i < list.Count; i++)
                if(list[i].CompareTo(list[i-1])<0) return false;
            return true;
        }
 
        private static void Shuffle<T>(this IList<T> list)
        {
            Random rand = new Random();
            for (int i = 0; i < list.Count; i++)
            {
                int swapIndex = rand.Next(list.Count);
                T temp = list[swapIndex];
                list[swapIndex] = list[i];
                list[i] = temp;
            }
        }
    }
 
    class TestProgram
    {
        static void Main()
        {
            List<int> testList = new List<int> { 3, 4, 1, 8, 7, 4, -2 };
            BogoSorter.Sort(testList);
            foreach (int i in testList) Console.Write(i + " ");
        }
 
    }
}

Go

package main
 
import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)
 
func main() {
    list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
    rand.Seed(time.Now().UnixNano())
    fmt.Println("unsorted:", list)
    temp := make([]int, len(list))
    copy(temp, list)
    for !sort.IntsAreSorted(temp) {
        for i, v := range rand.Perm(len(list)) {
            temp[i] = list[v]
        }
    }
    fmt.Println("sorted!  ", temp)
}

Java

public class BogoSort 
{
	public static void main(String[] args)
	{
		//Enter array to be sorted here
		int[] arr={4,5,6,0,7,8,9,1,2,3};
 
		BogoSort now=new BogoSort();
		System.out.print("Unsorted: ");
		now.display1D(arr);
 
		now.bogo(arr);
 
		System.out.print("Sorted: ");
		now.display1D(arr);
	}
	void bogo(int[] arr)
	{
		//Keep a track of the number of shuffles
		int shuffle=1;
		for(;!isSorted(arr);shuffle++)
			shuffle(arr);
		//Boast
		System.out.println("This took "+shuffle+" shuffles.");
	}
	void shuffle(int[] arr)
	{
		//Standard Fisher-Yates shuffle algorithm
		int i=arr.length-1;
		while(i>0)
			swap(arr,i--,(int)(Math.random()*i));
	}
	void swap(int[] arr,int i,int j)
	{
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	boolean isSorted(int[] arr)
	{
 
		for(int i=1;i<arr.length;i++)
			if(arr[i]<arr[i-1])
				return false;
		return true;
	}
	void display1D(int[] arr)
	{
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
 
}

JavaScript

shuffle = function(v) {
    for(var j, x, i = v.length; i; j = Math.floor(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x);
    return v;
};
 
isSorted = function(v){
    for(var i=1; i<v.length; i++) {
        if (v[i-1] > v[i]) { return false; }
    }
    return true;
}
 
bogosort = function(v){
    var sorted = false;
    while(sorted == false){
        v = shuffle(v);
        sorted = isSorted(v);
    }
    return v;
}

Julia

function bogosort!(arr::AbstractVector)
    while !issorted(arr)
        shuffle!(arr)
    end
    return arr
end
 
v = rand(-10:10, 10)
println("# unordered: $v
 -> ordered: ", bogosort!(v))

Kotlin

// version 1.1.2
 
const val RAND_MAX = 32768 // big enough for this
 
val rand = java.util.Random()
 
fun isSorted(a: IntArray): Boolean {
    val n = a.size
    if (n < 2) return true
    for (i in 1 until n) {
        if (a[i] < a[i - 1]) return false
    }
    return true
}
 
fun shuffle(a: IntArray) {
    val n = a.size
    if (n < 2) return
    for (i in 0 until n) {
        val t = a[i]
        val r = rand.nextInt(RAND_MAX) % n
        a[i] = a[r]
        a[r] = t
    }
}
 
fun bogosort(a: IntArray) {
   while (!isSorted(a)) shuffle(a)
}
 
fun main(args: Array<String>) {
    val a = intArrayOf(1, 10, 9,  7, 3, 0)
    println("Before sorting : ${a.contentToString()}")
    bogosort(a)
    println("After sorting  : ${a.contentToString()}")
}

MATLAB / Octave

function list = bogoSort(list)  
    while( ~issorted(list) ) %Check to see if it is sorted
        list = list( randperm(numel(list)) ); %Randomly sort the list
    end
end

Perl

use List::Util qw(shuffle);
 
sub bogosort
 {my @l = @_;
  @l = shuffle(@l) until in_order(@l);
  return @l;}
 
sub in_order
 {my $last = shift;
  foreach (@_)
     {$_ >= $last or return 0;
      $last = $_;}
  return 1;}

Perl 6

sub bogosort (@list is copy) {
    @list .= pick(*) until [<=] @list;
    return @list;
}
 
my @nums = (^5).map: { rand };
say @nums.sort.Str eq @nums.&bogosort.Str ?? 'ok' !! 'not ok';

PHP

function bogosort($l) {
    while (!in_order($l))
        shuffle($l);
    return $l;
}
 
function in_order($l) {
    for ($i = 1; $i < count($l); $i++)
        if ($l[$i] < $l[$i-1])
            return FALSE;
    return TRUE;
}

PowerShell

function shuffle ($a) { 
    $c = $a.Clone()  # make copy to avoid clobbering $a
    1..($c.Length - 1) | ForEach-Object {
        $i = Get-Random -Minimum $_ -Maximum $c.Length
        $c[$_-1],$c[$i] = $c[$i],$c[$_-1]
        $c[$_-1]  # return newly-shuffled value
    }
    $c[-1]  # last value
}
 
function isSorted( [Array] $data )
{
	$sorted = $true
	for( $i = 1; ( $i -lt $data.length ) -and $sorted; $i++ )
	{
		$sorted = $data[ $i - 1 ] -le $data[ $i ]
	}
	$sorted
}
 
function BogoSort ( [Array] $indata ) {
	$data = $indata.Clone()
	while( -not ( isSorted $data ) ) {
		$data = shuffle $indata
	}
	$data
}
 
$l = 7; BogoSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )

Python

import random
 
def bogosort(l):
    while not in_order(l):
        random.shuffle(l)
    return l
 
def in_order(l):
    if not l:
        return True
    last = l[0]
    for x in l[1:]:
        if x < last:
            return False
        last = x
    return True

R

bogosort 

Ruby

def shuffle(l)
    l.sort_by { rand }
end
 
def bogosort(l)
    l = shuffle(l) until in_order(l)
    l
end
 
def in_order(l)
    (0..l.length-2).all? {|i| l[i] <= l[i+1] }
end

Rust

extern crate rand;
use rand::Rng;
 
fn bogosort_by(order: F, coll: &mut [T])
    where F: Fn(&T, &T) -> bool
{
    let mut rng = rand::thread_rng();
    while !is_sorted_by(&order, coll) {
        rng.shuffle(coll);
    }
}
 
#[inline]
fn is_sorted_by(order: F, coll: &[T]) -> bool
    where F: Fn(&T,&T) -> bool,
{
    coll[..].iter().zip(&coll[1..]).all(|(x,y)| order(x,y))
}
 
 
fn main() {
    let mut testlist = [1,55,88,24,990876,312,67,0,854,13,4,7];
    bogosort_by(|x,y| x < y, &mut testlist);
    println!("{:?}", testlist);
    bogosort_by(|x,y| x > y, &mut testlist);
    println!("{:?}", testlist);
}

Scala

def isSorted(l: List[Int]) = l.iterator sliding 2 forall (s => s.head <= s.last)
def bogosort(l: List[Int]): List[Int] = if (isSorted(l)) l else bogosort(scala.util.Random.shuffle(l))

Swift

import Darwin
 
func shuffle<T>(inout array: [T]) {
  for i in 1..<array.count {
    let j = Int(arc4random_uniform(UInt32(i)))
    (array[i], array[j]) = (array[j], array[i])
  }
}
 
func issorted<T:Comparable>(ary: [T]) -> Bool {
  for i in 0..<(ary.count-1) {
    if ary[i] > ary[i+1] {
      return false
    }
  }
  return true
}
 
func bogosort<T:Comparable>(inout ary: [T]) {
  while !issorted(ary) {
    shuffle(&ary)
  }
}

より多くのコードを更新し続けます!ネットワークから整理する.