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
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.
This challenge explores the efficiency (or lack of) of each of these three sorting algorithms. The golfed code will
generate a shuffled 8 element array of the integers 1-8 inclusive (keep reading to see how you should do this);
apply each algorithm to this array; and
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.
Bogosort, it should record the number of times the array was shuffled.
Bogoswap, it should record the number of swaps made.
Bogosmart, it should record the number of swaps made.
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.
- 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.
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,
Bogoswaponly 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.