8
\$\begingroup\$

Introduction

This challenge is about three (bad) sorting algorithms: Bogosort, and two others variants that I came up with (but have probably been thought of by others at some point in time): Bogoswap (AKA Bozosort) and Bogosmart.

Bogosort works by completely shuffling the array randomly and checking if it becomes sorted (ascending). If not, repeat.

Bogoswap works by selecting two elements, randomly, and swapping them. Repeat until sorted (ascending).

Bogosmart works by selecting two elements, randomly, and only swapping them if it makes the array closer to being sorted (ascending), ie. if the element with the lower index was originally larger than the one with the higher. Repeat until sorted.

The Challenge

This challenge explores the efficiency (or lack of) of each of these three sorting algorithms. The golfed code will

  1. generate a shuffled 8 element array of the integers 1-8 inclusive (keep reading to see how you should do this);

  2. apply each algorithm to this array; and

  3. display the original array, followed by the number of computations required for each algorithm, separated by one space (trailing space ok), in the format <ARRAY> <BOGOSORT> <BOGOSWAP> <BOGOSMART>.

The program will produce 10 test cases; you can generate all ten at the beginning or generate one at a time, whatever. Sample output below.

Details:

For Bogosort, it should record the number of times the array was shuffled.

For Bogoswap, it should record the number of swaps made.

For Bogosmart, it should record the number of swaps made.

Example output:

87654321 1000000 100 1
37485612 9050000 9000 10
12345678 0 0 0 
28746351 4344 5009 5
18437256 10000 523 25
15438762 10000 223 34
18763524 58924 23524 5
34652817 9283 21 445
78634512 5748 234 13
24567351 577 24 34

I made up these numbers; of course, your program will print different output but in the same format.

Rules

  • All randomness used in your program must come from pseudorandom number generators available to you, and otherwise not computed extensively by you. You don't have to worry about seeds.
  • There is no time limit on the programs.
  • The arrays are to be sorted ascendingly.
  • Trailing spaces or an extra newline is no big deal.
  • For Bogosort, the array is to be shuffled using any unbiased shuffling algorithm such as Fisher-Yates or Knuth Shuffling, explicitly specified in your explanation. Built-in shuffling methods are not allowed. Generate your test arrays in the same manner.
  • If after shuffling or swapping the array remains the same, it still counts and should be included in the program's count. For example, shuffling the array to itself by coincidence counts as a shuffle, and swapping an element with itself counts as a swap, even though none of these operations change the array.
  • If my memory serves me correctly, an 8 element array shouldn't take too long for any of the three algorithms. In fact, I think a few times for a 10 element array, when I tried it, Bogoswap only required a few thousand (or less) actual shuffles and well under 10 seconds.
  • Your code must actually sort the arrays, don't just give expected values or mathematical calculations for an expected answer.
  • This is a code-golf challenge, so shortest program in bytes wins.

Here are some sample steps for each sorting algorithm:

BOGOSORT
56781234
37485612
28471653
46758123
46758123
12685734
27836451
12345678

BOGOSWAP
56781234
16785234
17685234
12685734
12685743
12685734
12485763
12385764
12385764
12345768
12345678

BOGOSMART
56781234
16785234
12785634
12785364
12785364
12385764
12385674
12345678

In this case, the program would output 56781234 7 10 7, and then do the same thing 10 times. You do not have to print the arrays while sorting is going on, but I gave the above sample steps so you can understand how each algorithm works and how to count computations.

\$\endgroup\$
  • 2
    \$\begingroup\$ There are 8! = 40,320 possible orders for an 8 element array. My math is not good enough to translated this into the expected (average) number of bogosort steps. But intuitively, it should be at least within an order of magnitude of that number. My theory is that bogosort and bogoswap will require the same average number of steps. Only that one step of bogoswap is cheaper, so the time will be lower. \$\endgroup\$ – Reto Koradi Jun 4 '15 at 0:22
  • \$\begingroup\$ I've done this before, and believe me you will be amazed at how different your thoughts differ from reality. You will find that, not surprisingly, Bogosort has the largest number of computations, then surprisingly Bogoswap has a lower, and of course Bogosmart takes even fewer. You will also be surprised by how few computations Bogosort needs, well below 40320. \$\endgroup\$ – Faraz Masroor Jun 4 '15 at 0:26
  • \$\begingroup\$ In short, I don't expect this challenge to ruin your computer or swamp your memory. \$\endgroup\$ – Faraz Masroor Jun 4 '15 at 0:27
  • 2
    \$\begingroup\$ Related. (For the shuffling and Bogosort part.) \$\endgroup\$ – Martin Ender Jun 4 '15 at 0:32
  • \$\begingroup\$ Can we just output the number of steps from the mathematically correct distribution without doing the sorting? \$\endgroup\$ – xnor Jun 4 '15 at 0:40
3
\$\begingroup\$

Pyth, 62 60 bytes

VTjd[jkKJ=boO0=ZS8fqZ=KoO0K0fqZ=XJO.CJ2)0fqZ=Xb*>F=NO.Cb2N)0

This was quite fun. Not sure if this is valid, I'm probably using some unwritten loopholes.

A sample output would be:

23187456 22604 23251 110
42561378 125642 115505 105
62715843 10448 35799 69
72645183 7554 53439 30
61357428 66265 6568 77
62348571 1997 105762 171
78345162 96931 88866 241
17385246 51703 7880 80
74136582 36925 19875 100
26381475 83126 2432 25

Explanation:

My shuffle function uses the built-function order-by. Basically I assign each element of the list a random number of the interval [0-1) and sort the list by them. This gives me an unbiased random shuffle.

Outer loop

The VT at the start repeats the following code 10 times.

Preparation

jkKJ=boO0=ZS8
           S8        create the list [1, 2, 3, 4, 5, 6, 7, 8]
         =Z          and store in Z
      oO0            shuffle
    =b               and store in b
   J                 and store in J
  K                  and store in K (3 copies of the same shuffled array)
jkK                  join K with ""

Bogosort

fqZ=KoO0K0 
     oO0K            shuffle K
   =K                and store the result in K
f        0           repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

Bogoswap

fqZ=XJO.CJ2)0  
       .CJ2          give all possible pairs of elements of J
      O              take a random one
    XJ     )         swap these two elements in J
   =                 and store the result in J
f           0        repeat ^ until:
 qZ K                  Z == K
                     and give the number of repeats

Bogosmart

fqZ=Xb*>F=NO.Cb2N)0
            .Cb2     give all possible pairs of elements of b
           O         take a random one
         =N          assign it to N
       >F N          check if N[0] > N[1]
      *         N    multiply the boolean with N
    Xb           )   swap the two (or zero) values in b
   =                 and assign to b
f                 0  repeat ^ until:
 qZ                    Z == b
                     and give the number of repeats

Printing

jd[
  [                  put all 4 values in a list
jd                    join by spaces and print
\$\endgroup\$
  • \$\begingroup\$ =JXJO.cJ2) is the same as =XJO.cJ2) - augmented assignment. Same holds for =bXb later. Also, I think swaps are supposed are supposed to have the pairs chosen with replacement (.C) \$\endgroup\$ – isaacg Jun 4 '15 at 10:47
  • \$\begingroup\$ @isaacg Thanks, corrected things. Not sure if either .c or .C are allowed. For instance .C[3 1 2)2 doesn't return the pair [2, 1]. Which is a property, that I'm exploiting in my algorithm. \$\endgroup\$ – Jakube Jun 4 '15 at 11:20
  • \$\begingroup\$ maybe *JJ then? It's also one character shorter, which is nice. \$\endgroup\$ – isaacg Jun 4 '15 at 13:35
2
\$\begingroup\$

JavaScript (ES6), 319 345

Unsurprisingly this is quite long.

For Random shuffle, credits to @core1024 (better than mine for the same chellenge)

Test running the snippet (Firefox only as usual)

// FOR TEST : redefine console
var console = { log: (...p)=>O.innerHTML += p.join(' ')+'\n' }
// END 

// Solution
R=n=>Math.random()*n|0, 
S=a=>(a.map((c,i)=>(a[i]=a[j=R(++i)],a[j]=c)),a), // shuffle
T=f=>{for(a=[...z];a.join('')!=s;)f(a)}, // apply sort 'f'  algorithm until sorted

s='12345678';
for(i=0;i<10;i++)
  z=S([...s]),
  n=l=m=0,
  T(a=>S(a,++n)),
  T(a=>(t=a[k=R(8)],a[k]=a[j=R(8)],a[j]=t,++m)),
  T(a=>(t=a[k=R(8)],u=a[j=R(8)],(t<u?j<k:k<j)&&(a[k]=u,a[j]=t,++l))),
  console.log(z.join(''),n,m,l)
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ The "Run code snippet" link does not work for me. Not sure if it's my browser/system, but the snippet links have worked for me in the past. \$\endgroup\$ – Reto Koradi Jun 4 '15 at 15:56
  • \$\begingroup\$ Same, the code snippet doesnt work on my browser \$\endgroup\$ – Faraz Masroor Jun 4 '15 at 17:46
  • 2
    \$\begingroup\$ @Reto et al EcmaScript 6: run on Firefox only. \$\endgroup\$ – edc65 Jun 4 '15 at 18:00

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.