Fisher-Yates (java) vs. Collections.shuffle

Viewed 663

I'm still a beginner so please be kind. I have trouble understanding why the Fisher-Yates algorithm modifies the array elements permanently and the Collections' shuffle method doesn't. I suspect one reason is that I may not actually understand properly how the Fisher-Yates algorithm works, but I would appreciate any help. Code below:

import java.util.*;

public class ArrayShuffle {

private static char[] letters = {'a','b','c','d','e','f','g'};

public static void main(String[] args) {
    System.out.println("Collections' shuffle method:");
    shuffleCollections(letters);
    System.out.print(letters);
    System.out.println();
    System.out.println("Fisher-Yates method:");
    shuffleFisherYates(letters);
    System.out.print(letters);

}

public static void shuffleCollections(char[] abc) {
    List letterList = new ArrayList();
    for(int alph=0; alph<abc.length; alph++)
        //convert char to ArrayList object
        letterList.add(abc[alph]);
    //shuffle
    Collections.shuffle(letterList);
    System.out.println(letterList);


}

public static void shuffleFisherYates(char[] abc) {
    int size = abc.length;
    Random random = new Random();
    for(int alph=0; alph<abc.length; alph++) {
        int randomIndex = alph + random.nextInt(size - alph);
        char randomLetter = abc[randomIndex];
        abc[randomIndex] = abc[alph];
        abc[alph] = randomLetter;
    }
    for(int shuffled = 0; shuffled<abc.length; shuffled++)
        System.out.print(abc[shuffled]+" ");
    System.out.println();

}

}

1 Answers

Your shuffleFisherYates modifies the input array directly (that's what abc[someIndex] = ...; does).

Your shuffleCollections builds an ArrayList based on the input array and then modifies that ArrayList (via the call to Collections.shuffle(letterList)). It doesn't modify the input array.

Related