29
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ What are the element types? int or strings? \$\endgroup\$ – Alexandru Feb 2 '11 at 21:39
  • \$\begingroup\$ @Alexandru: Either is fine. You choose. \$\endgroup\$ – Chris Jester-Young Feb 2 '11 at 21:40
  • \$\begingroup\$ 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. \$\endgroup\$ – Alexandru Feb 2 '11 at 21:57
  • 1
    \$\begingroup\$ It's possible that this algorithm can fail when using pseudo random generator. eg when the length of the list exceeds say 2000, there are 2000! states for the list which may exceed the number of interal states of the prng. \$\endgroup\$ – gnibbler Feb 2 '11 at 22:38
  • 2
    \$\begingroup\$ 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." \$\endgroup\$ – gnibbler Feb 2 '11 at 23:30

40 Answers 40

0
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

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]

\$\endgroup\$
  • \$\begingroup\$ Return isn't a function, you don't need parenthesis... \$\endgroup\$ – FlipTack Feb 12 '17 at 21:25
  • \$\begingroup\$ you can use l<sorted(l) instead of != \$\endgroup\$ – gnibbler Feb 12 '17 at 23:10
0
\$\begingroup\$

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
    }
}
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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");
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.