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

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 2

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 3

Java, 252

Requires java 10 as the varkeyword is used.

import java.util.*;interface B{static int c(List<String>a,int i){return i>0?Math.max(a.get(i-1).compareTo(a.get(i)),c(a,i-1)):-1;}
static void main(String[]p){var a=Arrays.asList(p);while(c(a,a.size()-1)>0)Collections.shuffle(a);System.out.print(a);}}

Explained

import java.util.*;                              // you don't get a lot for free in java
interface B{
  static int c(List<String>a,int i){             // recursive comparator method, i is index to compare a[i-1] with a[i]
    return i>0?                                  // still not at the first element?
           Math.max(                             // return the max of...
             a.get(i-1).compareTo(a.get(i)),     // - string comparison of a[i-1] and a[i]
             c(a,i-1))                           // - recursive call c for i-1
           :-1;                                  // i=0 -> return -1
  }
  static void main(String[]p){                   // entry point
    var a=Arrays.asList(p);                      // convert the input array in a List (so we can use Collections functions)
    while(c(a,a.size()-1)>0)                     // as long as c()>0, at least one element is not in correct order
      Collections.shuffle(a);                    // shuffle the list
    System.out.print(a);                         // print the ordered list
  }
}

Try it online

Answer 4

05AB1E, 8 bytes

[Ð{Q#.r

Try it online!

Explanation:

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

Answer 5

Pushy, 8 bytes

[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 6

Vyxal, 8 bytes

{ÞṠ¬|Þ℅:

Try it Online!

Explanation

{ÞṠ¬|Þ℅:  # Implicit input
{   |     # While loop
 ÞṠ       # (Condition): Is sorted?
   ¬      #              Logical NOT
     Þ℅   # (Body): Randomly shuffle
       :  #         Duplicate
          # Implicit output

Answer 7

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 8

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 9

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 10

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 11

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

Answer 12

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 13

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 14

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 15

Husk, 8 bytes

ΩS=O§!←P

Try it online!

Husk does not have random numbers, so this uses the array itself to get a permutation. I genuinely don't know whether this would complete.

Explanation

ΩS=O§!←P
Ω        Until
 S=O     the argument is ordered
       P take it's permutations
      ←  take its first element
    §!   return that permutation

Answer 16

CJam, 14 bytes

{{__$=!}{mr}w}

Try it online!

Answer 17

Pyth, 13 11 bytes

WnSQKO.pQ;K

Previous Solution

L?n.SbSbybb
y

Try it online!

WnSQKO.pQ;K
      .pQ    Generate a list of all permutations of input
    KO.pQ    K = random permutation in the list
WnSQK    ;   While(sorted(input) != K): do nothing
          K  print K

Previous Solution:
Compiled to python:

assign('Q',eval_input())
@memoized
def subsets(b):
 return (subsets(b) if ne(shuffle(b),Psorted(b)) else b)
imp_print(subsets(Q))

Basically:
Shuffle the list, if it isn't equal to the sorted list:
recursively call.
Else:
Return it