2
\$\begingroup\$

Just checking that this shuffling algorithm is suitable. Or maybe there could be improvements?

public static void shuffleArray(Object[] arr, Random rnd){
    int lastIndex = arr.length - 1;
    for (int i=0; i<=lastIndex; i++){
        int k = nextInt(i,lastIndex+1, rnd);
        Object a = arr[i];
        Object b = arr[k];
        arr[i] = b;
        arr[k] = a;
    }
}

//Returns an integer between start(inclusive) and end(exclusive) [start..end) 
public static int nextInt ( int start, int end, Random rnd);
\$\endgroup\$
  • 1
    \$\begingroup\$ Those +1 and -1 hurt my eyes. \$\endgroup\$ – abuzittin gillifirca Jun 13 '13 at 14:33
  • 1
    \$\begingroup\$ Hmm, there is Collections.shuffle(), any reason why you don't use that? \$\endgroup\$ – fge Jun 13 '13 at 15:20
  • \$\begingroup\$ I wish to shuffle an array of byte(s). And I believe it will be tedious todo type conversions, etc. \$\endgroup\$ – Kurent Jun 13 '13 at 16:05
  • \$\begingroup\$ stackoverflow.com/a/1520212/59087 \$\endgroup\$ – Dave Jarvis Jun 13 '13 at 16:55
1
\$\begingroup\$

One small thing is during the last iteration of the loop, the last element is swapped with itself.

Why not just use the Collections.shuffle as a guide?

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

private static void swap(Object[] arr, int i, int j) {
    Object tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

This could be altered to:

public static void shuffleArray(Object[] arr, Random rnd) {
    for (int i=arr.length; i>1; i--) {
        int j = rnd.nextInt(i);
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
\$\endgroup\$
  • \$\begingroup\$ This is very helpful, I spotted the last element self-swap too. However,j in your example is being restricted in a similar way to k. \$\endgroup\$ – Kurent Jun 13 '13 at 17:25
  • \$\begingroup\$ @Kurent Ah, you're right about j, I didn't see that. Nice catch, I'll edit my answer. \$\endgroup\$ – kuporific Jun 13 '13 at 18:15

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.