3
\$\begingroup\$

Since I did not get a satisfactory answer here (and I really needed to get it going on this weekend), I decided to implement my own Fisher–Yates shuffle, porting the code I found in other SO posts. I know my programming technique is far from optimal, so I decided to post this here.

What do you think? Can it be improved?

public static JSONArray shuffleJsonArray (JSONArray array) throws JSONException {
    // Implementing Fisher–Yates shuffle
        Random rnd = new Random();
        for (int i = array.length() - 1; i >= 0; i--)
        {
          int j = rnd.nextInt(i + 1);
          // Simple swap
          Object object = array.get(j);
          array.put(j, array.get(i));
          array.put(i, object);
        }
    return array;
}
\$\endgroup\$
2
\$\begingroup\$

It runs in \$O(n)\$ time so I'm not sure there's a way to improve this. It looks like you've implemented the algorithm pretty well, according the Fisher-Yates shuffle.

You might consider not using Object if you can use the type that's stored in the array instead.

I also thought I read somewhere that it should be safe to loop to \$n/2\$ instead of \$n\$ (because you're swapping with elements from \$1 \cdots n\$ so in theory, you shouldn't need to swap every element), but I don't have hard proof of that, so you take your chances ;)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for looking at it. I based it on that wikipedia page and a couple of posts in SO. I will keep in mind the n/2 loops to change it if needed. Lastly, I wrote it using JSONObject instead of Object but then I changed it to make it more reusable. What would be the advantage of using JSONObject instead? \$\endgroup\$ – Aleadam Apr 4 '11 at 15:30
  • \$\begingroup\$ @Aleadam: I don't know the JSONArray datatype well, I guess I was trying to suggest to use Java generics so you don't have to use Object, but I don't know if you can do that with JSONArray. \$\endgroup\$ – FrustratedWithFormsDesigner Apr 4 '11 at 15:36
  • \$\begingroup\$ I also think that there is no faster way for shuffling an array. Every try in doing it faster (O(log n) or O(sqrt n)) would result in a poorly shuffled array. \$\endgroup\$ – leemes May 17 '12 at 20:58

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.