Implement Bogosort

Question

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. :-)

Answer 1

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 (∇)

---

Suddenly revisiting this problem and...

APL(Dyalog), 19

{∧/2≤/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Was just thinking about sorting an array in the check makes it kind of pointless (not saying that Bogosort is meaningful), a more accurate implementation would be ∧/2≤/⍵, and that happens to lower the char count.

Answer 2

Perl 6: 23 chars

@s.=pick(*)until[<=] @s

Answer 3

Ruby - 33 characters

g=->l{l.shuffle!!=l.sort ?redo:l}

Answer 4

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.

Answer 5

Mathematica, 40 37

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

With whitespace:

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

Answer 6

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

Answer 7

Python 61

Sorts in place.

import random
def f(l):
 while l!=sorted(l):random.shuffle(l)

Answer 8

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"

Answer 9

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.

Answer 10

GNU/BASH 65

b(){ IFS=$'\n';echo "$*"|sort -C&&echo "$*"||b $(shuf -e "$@");}

Answer 11

PowerShell, 85 82 56 55 52 bytes

^{-26 bytes thanks to mazzy's suggestions
-1 byte thanks to AdmBorkBork
-3 bytes thanks to mazzy}

for($l=$args;"$l"-ne($l|sort)){$l=$l|sort{random}}$l

Try it online!

PowerShell does have a relatively cheap array comparison by casting them to strings and comparing that.

Answer 12

Python - 61 chars

Recursive

from random import*;f=lambda l:l==sorted(l)or shuffle(l)>f(l)

Answer 13

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.

Answer 14

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

Answer 15

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. ;)

Answer 16

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

Answer 17

C++11, 150 characters

#include<deque>
#include<algorithm>
void B(std::deque &A){while(!std::is_sorted(A.begin(),A.end())std::random_shuffle(myvector.begin(),myvector.end());}

Just.. made for fun.

Answer 18

Jelly, 6 bytes, language postdates challenge

ẊŒ¿’$¿

Try it online!

Explanation

ẊŒ¿’$¿
     ¿  While
 Œ¿’$     the input is not in its earliest possible permutation (i.e. sorted)
Ẋ       shuffle it

Œ¿ assigns a number to each permutation of a list; 1 is sorted, 2 has the last two elements exchanged, etc., up to the factorial of the list length (which is the list in reverse order). So for a sorted list, this has the value 1, and we can decrement it using ’ in order to produce a "not sorted" test that's usable as a Boolean in a while loop condition. The $ is to cause the condition to parse as a group.

Answer 19

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

Answer 20

Brachylog (v2), 5 bytes

≤₁|ṣ↰

Try it online!

Function submission. (The TIO link uses a command-line argument that automatically wraps a function into a full program.)

Explanation

≤₁|ṣ↰
≤₁      Assert that {the input} is (nonstrictly) sorted in ascending order
  |     Output it
  |     Exception handler: if an assertion fails:
   ṣ      Randomly shuffle {the input}
    ↰     and run this function recursively on it, {outputting its output}

Prolog (the language that Brachylog compiles into) is tail-recursive, so this function ends up being compiled into a tight loop.

Answer 21

C++, 166 bytes

Meh.

#import<algorithm>
#import<random>
#define r b.begin(),b.end()
template<class v>
v f(v b){auto a=std::mt19937();while(!std::is_sorted(r))std::shuffle(r,a);return b;}

This should work on all STL containers that have begin() and end().

Ungolfed:

#include <algorithm>
#include <random>
template <class v>
v f(v b) {
    auto a = std::mt19937();
    while (!std::is_sorted(b.begin(),b.end()))
        std::shuffle(b.begin(),b.end(),a);

    return b;
}

Answer 22

APL (Dyalog Extended), 15 bytes

(?⍨∘≢⊇⊢)⍣{⍺≡∧⍺}

Try it online!

Answer 23

Brachylog, 5 bytes

∈&ṣ≤₁

Try it online!

When I first saw ais523's Brachylog answer (as opposed to his Jelly answer, because if I'm not mistaken user62131 was also him), I wondered, what if it used backtracking instead of recursion? So at first, I tried ṣ≤₁. Turns out, since choosing something at random doesn't produce multiple outputs so much as it just produces one output nondeterministically, the shuffle predicate ṣ can't be backtracked to, so running that will simply fail unless you're lucky enough to shuffle it right on the first try. After that, I tried pṣ≤₁, which worked most of the time, but since a finitely long list has finitely many permutations, it still failed at random sometimes. After having abandoned the goal of achieving length reduction, I finally came up with this:

         The input
∈        is an element of
         an unused implicit variable,
 &       and the input
  ṣ      shuffled randomly
   ≤₁    which is increasing
         is the output.

(Demonstration of randomness)

Although it actually can be a bit shorter if we take some liberties with I/O...

Brachylog, 4 bytes

⊆ṣ≤₁

Try it online!

In order for the output to be useful, the input must not contain any duplicate elements, because in addition to sorting the input, this bogosort predicate adds in a random number of duplicate elements and zeroes. (Hypothetically, it could add in anything, but it just kind of doesn't.) Ordinarily I wouldn't bother mentioning something so far from correctly functioning, but I feel it's in the spirit of the challenge.

⊆        An ordered superset of the input
 ṣ       shuffled randomly
  ≤₁     which is increasing
         is the output.

Answer 24

Japt, 11 9 bytes

_eZñ}a@öx

Try it

_eZñ}a@öx     :Implicit input of array U
_             :Function taking an array as argument via parameter Z
 e            :  Test Z for equality with
  Zñ          :  Z sorted
    }         :End function
     a        :Repeat and return the first result that returns true
      @       :Run this function each time and pass the result to the first function
       öx     :  Random permutation of U

Answer 25

Perl 6, 28 bytes

{({.pick(*)}...~.sort).tail}

Try it online!

Anonymous code block that shuffles the list until it is sorted. Note that it sorts the list at least once, which is allowed. And no, the {.pick(*)} can't be replaced with *.pick(*)

Answer 26

Pyth, 11 bytes

Wn=Q.SQSQ;Q

Pretty happy with this, probably can be golfed a bit more

Explanation

Wn=Q.SQSQ;Q
W    While
  =Q.SQ    Variable Q (input variable) shuffled 
 n  Does not equal
       SQ    Variable Q sorted
             ;  Do nothing (loop ends)
              Q    And output variable Q

Try it online!

Answer 27

Matlab, 59 bytes

Relatively straight forward approach:

x=input('');while~issorted(x);x=x(randperm(numel(x)));end;x

Answer 28

J, 22 bytes

$:@({~?~@#)`]@.(-:/:~)

This is a recursive, tacit monad using an agenda. Here's how it works:

Let y be our list. First, the verb on the right of the agenda is -:/:~. This a verb graciously provided by Leaky Nun. It matches (-:) whether or not the input is sorted (/:~) using a monadic hook. ((f g) y = y f (g y)) This returns a one or a zero accordingly. The left hand side of the agenda is a gerund of two verbs: on the right is the identity verb ], and on the left is where the recursion takes place. The agenda selects either the identity verb at position 1 if the list is sorted, and the longer verb at position 0 if the list isn't sorted.

$:@({~?~@#) calls $: (the longest verb it is contained in) atop the result of {~?~@# on y. This shuffles the list, as ?~@# takes the permutations of the length of y, being randomly-sorted indices of y. {~, in a monadic hook, returns a list from y whose indices are the right arg. This shuffled list is then called again with the agenda, and repeats until it is sorted.

Answer 29

C++14, 158 bytes

#include <algorithm>
#include <random>
[](int*a,int s){std::random_device r;for(std::knuth_b g(r());!std::is_sorted(a,a+s);std::shuffle(a,a+s,g));return a;};

Answer 30

Pushy, 8 bytes

Non competing as the language postdates the challenge.

[oSog?_i

Try it online!

Alternatively, run this version to see it print each shuffle as it goes along! The code works like this:

[          \ Infinitely:
 oS        \   Shuffle the stack
   og?     \   If it's sorted (ascendingly):
      _i   \     Print and terminate

If you want to sort descendingly, just replace og with oG.

Answer 31

C, 111 bytes

This answer takes bogus sort one step further: It doesn't shuffle the entire array before rechecking, it just makes a singe random swap before rechecking. For extra measure, that single random swap always swaps with the first entry, so the general random swap actually takes two iterations. Inefficient, yes, but hey, it's bogus sort, and it saves one call to rand()!

#include<stdlib.h>
t,r;b(int*d,int s){r=rand()%s;t=*d;*d=d[r];d[r]=t;for(r=s-1;r--;)d[r]>d[r+1]&&(b(d,s),r=0);}

Note that since the mixing loop is implemented via recursion, this will crash for larger input arrays (= more than eight elements on my machine) due to stack exhaustion.

Ungolfed:

void b(int*data,int size){
    //First, swap random element with the first element.
    int randomIndex = rand()%size;
    int temp = *data;
    *data = data[randomIndex];
    data[randomIndex] = temp;

    //Check if array is sorted
    for(int i = size-1;i--;) {
        if(data[i]>data[i+1]) {
            //array is not sorted, start over
            b(data,size);
            i = 0;  //don't resume loop on return
        }
    }
}

Test with

int main(){
    int data[] = {8, 7, 6, 5, 4, 3, 2, 1};
    int size = sizeof(data)/sizeof(*data);
    for(int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");

    b(data, size);

    for(i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");
}

Answer 32

SmileBASIC, 104 81 bytes

DEF B A@D
SWAP A[0],A[RND(LEN(A))]FOR I=0TO LEN(A)-2IF A[I]<A[I+1]GOTO@D
NEXT
END

Answer 33

05AB1E, 8 bytes

(non-competing; question predates the language)

[Ð{Q#.r

Try it online!

Explanation:

[        # Infinite Loop start
 Ð       # Push input
  {Q#    # If input is sorted, break loop
     .r  # Otherwise, shuffle

Answer 34

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).

Answer 35

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}

Answer 36

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}

Answer 37

05AB1E, 6 bytes

œ.ΔD{Q

Try it online!

Explanation

œ       Create list with all permutations
 .Δ     Return the first element that satisfies the followng:
   D{Q  Check if element is sorted.

Answer 38

Python, 71 characters

from random import*
def b(l):
 while l!=sorted(l):shuffle(l)
 return(l)

Not the shortest one, but it works.

Ungolfed:

from random import *
def bogosort(list):
    while list != sorted(list):
        shuffle(list)

    return(list)

Usage:

Input: b([1, 7, 3, 9, 2])

Output: [1, 2, 3, 7, 9]

Answer 39

Java - 207 bytes

boolean sorted(Integer[] n,int i){while(i-->1)if(n[i]<n[i-1])return false;return true;}void bogo(Integer[] n){List<Integer>l=Arrays.asList(n);while(!sorted(n,n.length)){Collections.shuffle(l);l.toArray(n);}}

Ungolfed try online

boolean sorted(Integer[] n,int i)
{
    while(i --> 1) // i..1
        if(n[i] < n[i-1]) // ascending order
            return false;

    return true;
}

void bogo(Integer[] n)
{
    List<Integer>l = Arrays.asList(n);

    while(!sorted(n, n.length))
    {
        Collections.shuffle(l); // shuffle
        l.toArray(n); // re-fill the array
    }
}

Answer 40

Java, 147 bytes

import java.util.*;void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

This sorts in ascending order, To make it sort in descending order, simply replace b.get(B-1)>b.get(B) with b.get(B-1)<b.get(B).

Ungolfed:

import java.util.*;

void A(List<Long> b) {
    for (;;) {
        for (int B = 1; B++ < b.toArray().length;) {
            if (b.get(B - 1) > b.get(B))
                break;
            return;
        }
        Collections.shuffle(b);
    }
}

Making this function compilable costs 9 bytes, resulting in a 156-byte program:

import java.util.*;class a{void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}}

---

Java (lambda expression), 111 bytes

(b,B)->{for(;;){for(B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

This is a java.util.function.BiConsumer<java.util.List<Long>, Integer>.