# Implement Bogosort

Is solving Sudoku too hard? Even the brute force version? Here's a coding exercise that's a little easier. I hope. :-P

Write the shortest function to implement bogosort. In specific, your function should:

• Take an array (or your language's equivalent) as input
• Check if its elements are in sorted order; if so, return the array
• If not, shuffle the elements, and start again

The shortest entry wins. In the case of a tie, a function that supports a custom comparator (and/or pseudorandom number generator) is favoured. Any remaining ties are resolved by favouring the earlier submission.

Clarifications: You can use any element type you want, as long as there's some way to order them, of course. Also, the shuffling has to be uniform; none of this "I'll just quicksort it and call it shuffled" business. :-)

-
What are the element types? int or strings? –  Alexandru Feb 2 '11 at 21:39
@Alexandru: Either is fine. You choose. –  Chris Jester-Young Feb 2 '11 at 21:40
Adding a custom comparator will increase the code length so a winning entry will not have a custom comparator. I think breaking the tie doesn't make sense. –  Alexandru Feb 2 '11 at 21:57
@Alexandru: If you have to code your comparison by hand (e.g., in GolfScript), making it support custom comparators is easy. However, your point is generally valid. –  Chris Jester-Young Feb 2 '11 at 21:59
Yes, the relevant quote from wikipedia "However, if a pseudorandom number generator is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior." –  gnibbler Feb 2 '11 at 23:30

## APL(Dyalog), 20

``````{⍵≡⍵[⍋⍵]:⍵⋄∇⍵[?⍨⍴⍵]}
``````

Explanation

`⍵` is the (right) argument
`⍵≡⍵[⍋⍵]`: Checks if `⍵` sorted equals `⍵` itself
`:⍵`: If yes, then return `⍵`
`∇⍵[?⍨⍴⍵]`: Else, generate an array of 1 to `⍴⍵` (length of `⍵`) in random order, reorder `⍵` according to that (`⍵[...]`), and apply the function to it (`∇`)

-

## Perl 6: 23 chars

``````@s.=pick(*)until[<=] @s
``````
-
Is this a function in perl? It looks nice :) –  Eelvex Feb 3 '11 at 18:14
If you don't know, `[<=]` checks if a list is sorted: `[<=] (1, 2, 3,) == (1 <= 2 <= 3) == (1 <= 2) and (2 <= 3)`, and `.pick(n)` chooses n random elements from a list, and `.pick(*)` lets Perl pick all elements. use.perl.org/~masak/journal/40459 –  SHiNKiROU Feb 4 '11 at 1:47
This must be Perl 6. I've never seen `pick` used before, let alone `[<=]`. Where in the documentation are those? –  GigaWatt Oct 15 at 20:33

## Ruby - 33 characters

``````g=->l{l.shuffle!!=l.sort ?redo:l}
``````
-
1 char less: `g=proc{|l|0until l.sort==l.shuffle!}` –  AShelly Jan 31 '12 at 21:59
@AShelly, your version doesn't work. My version (5 chars less) `f=->l{l.sort!=l.shuffle!?redo:l}` (Ruby 1.9) –  Łukasz Niemier Mar 11 '12 at 20:07
can someone please explain to me why `redo` works with a `proc` but not in a classical method with `def...end`? I thought `redo` only works with loops? –  padde Jul 27 '12 at 20:19
Ok never mind, i found something in 'The Ruby Programming Language' book: ”`redo` […] transfers control back to the beginning of the proc or lambda“. It simply is that way. –  padde Jul 27 '12 at 20:26

### APL (22)

``````{(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]}
``````

Usage:

``````    {(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]} 3 2 1
1 2 3
``````

Explanation:

• `⍋⍵`: returns the indexes of the items in sorted order, so `⍋30 10 20` gives `2 1 3`
• `(⍳X←⍴⍵)≡⍋⍵:⍵` Store the length of input list in X. If range `[1..X]` is equal to the sorted index order, the list is sorted, so return it.
• `⋄∇⍵[X?X]`: if this is not the case, recurse with shuffled array.
-

## C 512

All those unreadable answers, pshh. This one shows you what should be happening.

``````#define B0GO }return main(0,v);}
#define BGOO return puts(*(v+1));
#define BOGO j;main(c,v)char**v;{
#define BOOG s:
#define GBOO int k;k=&k;k%=c;
#define GOBO j=v[1][k];v[1][k]=v[1][c];v[1][c]=j;
#define OBGO for(j=1;v[1][j];)
#define OBOG for(;v[1][c];++c){
#define OGBO if(v[1][j-1]>v[1][j++])
#define OGOB goto s;
BOGO
OBGO
OGBO
OGOB
BGOO
BOOG
OBOG
GBOO
GOBO
B0GO
``````

(Note the PNRG is really, really horrible. This will fail for longer inputs)

-

## J - 34 27

``````f=:({~?~@#)^:(1-(-:/:~))^:_
``````

eg:

``````f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo
``````

The {~ ?~@# part shuffles the input:

``````({~ ?~@#) 1 9 8 4
4 8 9 1
({~ ?~@#) 'abcd'
bdca
``````
-

### Mathematica, 40 37

``````NestWhile[RandomSample,#,Sort@#!=#&]&
``````

With whitespace:

``````NestWhile[RandomSample, #, Sort@# != # &] &
``````
-

## Python 61

Sorts in place.

``````import random
def f(l):
while l!=sorted(l):random.shuffle(l)
``````
-
Your function does not return the array on success. –  hallvabo Feb 3 '11 at 13:47
Sorts in place. The passed array is modified. –  Alexandru Feb 3 '11 at 14:38
The question does say that the function is supposed to return the array though - even if it isn't technically necessary to get the result. –  Jonathan M Davis Feb 3 '11 at 18:01
`from random import*` can save a char. –  ugoren May 28 '12 at 10:39
This may not always work: (from python random module documentation): "Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated." –  Matt Jul 27 '12 at 17:06

# K, 31 25

`{while[~x~x@<x;x:x@(-#x)?#x];x}`

``````{x@(-#x)?#x}/[{~x~x@<x};]
``````

.

``````k){x@(-#x)?#x}/[{~x~x@<x};] 3 9 5 6 7 9 1
`s#1 3 5 6 7 9 9
``````

.

``````k){x@(-#x)?#x}/[{~x~x@<x};] "ascsasd"
`s#"aacdsss"
``````
-

## Python - 61 chars

Recursive

``````import random;f=lambda l:l==sorted(l)or random.shuffle(l)>f(l)
``````
-
Your function returns True or False, not the array. –  hallvabo Feb 3 '11 at 13:49
Also note that recursive solutions are doomed to failure even for small inputs. –  hallvabo Feb 3 '11 at 14:00
@hallvabo: I actually want to write a tail-recursive solution in Scheme, which won't deplete your stack, of course. –  Chris Jester-Young Feb 3 '11 at 15:35
@hallvabo, Alexandru had already done the obvious Python solution, so I was just going for something different here. Of course the recursive solution is just for fun and not a serious contender –  gnibbler Feb 3 '11 at 19:48

## Python (69 chars)

``````from random import*
def f(a):
while a>sorted(a):shuffle(a)
return a
``````

Sorts integers in increasing numeric order. Note that recursive solutions, like

`from random import*;f=lambda a:a>sorted(a)and(shuffle(a)or f(a))or a`

will fail due to stack overflow for even small inputs (say N>5), because Python does not do tail-call optimisation.

-

# D without custom comparator: 59 Characters

``````R f(R)(R r){while(!isSorted(r))r.randomShuffle();return r;}
``````

More Legibly:

``````R f(R)(R r)
{
while(!r.isSorted)
r.randomShuffle();

return r;
}
``````

# D with custom comparator: 69 Characters

``````R f(alias p,R)(R r){while(!isSorted!p(r))r.randomShuffle();return r;}
``````

More Legibly:

``````R f(alias p, R)(R r)
{
while(!isSorted!p(r))
r.randomShuffle();

return r;
}
``````
-

### Scala 73:

``````def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random.shuffle l)
``````

In Scala, we can check whether the compiler did a tail-call optimization:

``````@annotation.tailrec
def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random shuffle l)
``````

and yes, it did. However, for a short List of 100 values:

``````val rList = (1 to 100).map(x=>r.nextInt (500))
s(rList)
``````

took nearly 4 months to complete. ;)

-

# Python 94

``````from itertools import*
def f(a):return [x for x in permutations(a) if x==tuple(sorted(a))][0]
``````

Other python answers use random.shuffle(). The documentation of the python random module states:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

-

C# (184 chars)

``````T[]S<T>(T[]i)where T:IComparable<T>{T l=default(T);while(!i.All(e=>{var r=e.CompareTo(l)>=0;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=default(T);}return i.ToArray();}
``````

It's not really nice to do this in C#. You have to support generics to support both value and reference types. There is no array shuffle function or function to check if something is sorted.

Does anybody got any tips to make this better?

Edit Version that only sorts int (134 chars):

``````int[]S(int[]i){var l=0;while(!i.All(e=>{var r=e>=l;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=0;}return i.ToArray();}
``````
-

# GNU/BASH 65

``````b(){ IFS=\$'\n';echo "\$*"|sort -C&&echo "\$*"||b \$(shuf -e "\$@");}
``````
-
Hmm, can I get a special exception to the return the array rule since bash functions can only literally return an unsigned byte? –  kojiro Oct 16 at 2:03

# Javascript 291 characters

min

``````function f(e){var t=[].concat(e).sort();t.e=function(e){var n=true;t.forEach(function(t,r){if(t!=e[r])n=false});return n};while(!t.e(e.sort(function(){return Math.floor(Math.random()*2)?1:-1}))){console.log(e)}return e}
``````

un-min

``````function f(a) {
var b = [].concat(a).sort();
b.e = function (z) {
var l = true;
b.forEach(function (v, i) {
if (v != z[i]) l = false;
});
return l
};
while (!b.e(a.sort(function () {
return Math.floor(Math.random() * 2) ? 1 : -1;
}))) {
console.log(a);
}
return a;
}
``````
-

## C (203 chars, no input loop: only the func)

``````#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,v;s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}
``````

This is the same as the following, where we also read the array from stdin and write out the sorted array. Since the Q asked for the function and not a whole program...

## C (296 chars)

``````#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,n,v,x[999];s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F j=rand()%n;v=a[i];a[i]=a[j];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}main(){while(scanf("%d",&v)==1)x[n++]=v;if(!s(x,n))b(x,n);F printf("%d\n",x[i]);}}
``````

Compiling may give warning (implicit declarations). Hardencoded array size limit of 999 elements. Fragile.

if there's no need to pre-check if the array is sorted, it can be done in 284.

## C (251 chars, was 284)

``````#include <stdio.h>
#define F for(i=0;i<n;i++){
int i,j,n,v,a[999];s(int n){F if(a[i]>a[i+1])return 0;}return 1;}void h(){F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b(){while(!s(n-1))h();}main(){while(scanf("%d",&a[n++])>0);b();F printf("%d\n",a[i]);}}
``````

(using globals instead of function args).

-

## R, 82 characters

Since I wrote it for this question I thought I'll add it there as well. Slightly modified here to accomodate question criteria.

``````b=function(a){while(any(apply(embed(a,2),1,function(x)x[1]<x[2]))){a=sample(a)};a}
``````
-

## JavaScript (using Array.sort()): 91

Utilising Array.sort():

``````function s(a){while((a=a.sort(function(){return 2-Math.random()*4|0}))!=a.sort());return a}
``````

## JavaScript (avoiding Array.sort()): 186

Not using the built-in .sort() method (randomising method stolen from here):

``````function s(a){while(function(b,c,d){for(;c<b.length-1;){d&=b[c]<=b[++c]}return!d}(function(t,n,i){i=a.length;while(i--){n=Math.random()*i|0,t=a[i],a[i]=a[n],a[n]=t}}()||a,0,1));return a}
``````
-

python (56 characters)

``````def f(l):
from random import *
while shuffle(l) or l!=sorted(l):
pass
``````

it does not need to return

-
when down vote please mention why ? –  Sarathsp Aug 24 at 2:31
Just guessing: maybe was downvoted because it should return the sorted array. –  manatwork Aug 24 at 11:14
after calling this try printing l it will be sorted no need to return sorted array –  Sarathsp Sep 2 at 10:23
@Sarathsp that's all well and good, but the question clearly specifies return the array. –  kojiro Oct 13 at 17:52

# Scheme (fuck the character count!)

``````(use srfi-27 srfi-43 srfi-95)

(define r (random-source-make-integers
default-random-source))

(define (bogosort v)
(let f ()
(if (sorted? v) v
(begin
(vector-for-each
(lambda (i x)
(vector-swap! v i
(r (vector-length v) n))) v) (f)))))
``````
-
Code-golf is all about the character count. So you can't just f*** it. –  ugoren Oct 20 '12 at 14:20