Bogosort function loop in javascript

Question

I want to make bogosort function. I want to invoke the bogo function each time the output is false. I tried with do {bogo function block} while(sorted===false) loop but looped only once (arr changed to empty array). The final goal is to invoke function f.e bogo([1,5,3,2]) and it should output sorted array (in variable shuffled).

function bogo(arr) {

  function shuffle(arr) {
    var shuffled = [];
    var rand;
    while (arr.length !== 0) {
      rand = Math.floor(Math.random() * arr.length)
      shuffled.push(arr.splice(rand, 1)[0]);
    }
    return shuffled;
  }

  function sorted(shuffle) {
    for (var i = 0; i < shuffle.length - 1; i++) {
      if (shuffle[i] <= shuffle[i + 1]) {
        continue;
      } else {
        return false;
      }
    }
    return true
  }
  return sorted(shuffle(arr));
}

console.log(bogo([1, 2]));

your `sorted` function doesn't change anything, how would the array ever get sorted? also, `sorted` returns true or false ... not the (will never be) sorted array — Jaromanda X, Feb 28 '17 at 00:25
yes purpose of sorted is to output boolean. On that assumption the while function should take currently shuffled variable and show it but that's only my theory. — Felnyr, Feb 28 '17 at 00:35
the only `while` in your code is in `shuffle` ... that's run and finished by the time `sorted` is called — Jaromanda X, Feb 28 '17 at 00:36
I mean look at this bogo function as first iteration of `while` function that i should add later, but dont know how. Something like `while(bogo(arr)===false){bogo(arr)}`. I hope now you understend what i want to accomplish. — Felnyr, Feb 28 '17 at 00:40
When i try this code in node js console nad invoke `bogo ([1,2])` it otputs sometimes true sometimes false so this works now it should have been automatically invoked until it gets `true` — Felnyr, Feb 28 '17 at 00:43
So you want to randomly shuffle the array until it happens to be sorted? *arr* ends up empty because you *splice* all its elements in the shuffle. — RobG, Feb 28 '17 at 02:41
You should understand that bogosort could take a very, very long time for small arrays, and might not ever finish. For example, there are 10! (that's 10 factorial, or about 3.6 million) permutations in an array of 10 items. On average, bogosort will have to try half of them. 100! is about 9*10^157. It's unlikely that you'll see bogosort actually finish with a 100-element array. And, depending on how your random number generator works, it might be impossible to randomly generate all 100! permutations. — Jim Mischel, Feb 28 '17 at 19:12
@Jim Mischel I understand that the time to sort rises exponentialy when u add another value to array. This code is only for learning purposes :) — Felnyr, Feb 28 '17 at 19:31
Actually, bogosort is factorial time, not exponential time. Just be prepared to kill your program when it starts taking too long. — Jim Mischel, Feb 28 '17 at 19:36

score 2 · Accepted Answer · answered Feb 28 '17 at 13:07

If you want to shuffle the array until it's sorted, then you need a loop. You could use for, while or do, I think do is more semantic in this case.

Since you destroy the source array during the shuffle, you need to make sure the new shuffled array is passed each time, so:

function bogo(arr) {
  var shuffleCount = 0;
  function shuffle(arr) {
    var shuffled = [];
    var rand;
    while (arr.length !== 0) {
      rand = Math.floor(Math.random() * arr.length)
      shuffled.push(arr.splice(rand, 1)[0]);
    }
    return shuffled;
  }

  function sorted(shuffle) {
    for (var i = 0; i < shuffle.length - 1; i++) {
      if (shuffle[i] <= shuffle[i + 1]) {
        continue;
      } else {
        return false;
      }
    }
    return true
  }
  
  do {
    shuffleCount++;
    arr = shuffle(arr);
  } while (!sorted(arr))
  
  return shuffleCount + ' | ' + arr.join();
}

console.log(bogo([1, 2,3,4]));

@Is there any solution to use initial arr for every shuffling not the shuffled already? — Felnyr, Feb 28 '17 at 13:21
You need to modify the *shuffle* function to shuffle the array in place, see [*How to randomize (shuffle) a JavaScript array?*](http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array) — RobG, Feb 28 '17 at 22:49

Bogosort function loop in javascript

1 Answers1