Shuffling array of ints

[russell lloyd]

I am writing a method for a CS assignment that is supposed to take in an array of ints and return the array shuffled. I read elsewhere on these boards where someone explained how to do this but with strings. I tried to follow their code making the appropriate changes for ints but I am having a problem.

    public static int[] shuffle(int[] original)
    {   assert original != null : "Violation of precondition: shuffle";
        //declare the variables of the new array as well as an array to make sure we don't copy elements into the same spot
        Random r = new Random();
        int [] newArray = new int[original.length];
        boolean [] checkerArray = new boolean[original.length];
        
        //for loop TIME
        for(int i = 0; i< newArray.length;i++)
        {
           while(newArray[i] == 0)
            {
                 int newRandom = r.nextInt(original.length);
                if(checkerArray[newRandom] == false)
                {
                    newArray[i] = original[newRandom];
                    checkerArray[newRandom] = true;
                    System.out.println("newArray[i] " + newArray[i]);
                }
            }
        }
                
        for (int k = 0; k < newArray.length; k++)
        {
            System.out.println("newArray["+k+"] = " + newArray[k]);
        }
        
        
        return newArray;
    } 

the code works fine as long as original doesn't contain 0's but if it does then it results in an infinite loop I was wondering how I could maybe modify the code so that it could avoid this

[Michael Dunn]

here's a slightly different approach

public static int[] shuffle(int[] original)
{   
  Random r = new Random();
  int [] newArray = new int[original.length];
  //add an arraylist
  //a for loop to add the element numbers of newArray to the arraylist (add as Integer())       
  for(int i = 0; i< newArray.length;i++)
  {
     //generate r.nextInt(arraylist.size())
     //newArray[x] = original[intValue of (arraylist.get(generated random number) cast to Integer)]           
     //arraylist.remove(generated random number)   
  }     
  return newArray;
} 
 

[Kenneth Albertson]

Originally posted by russell lloyd:
The code works fine as long as original doesn't contain 0's but if it does then it results in an infinite loop I was wondering how I could maybe modify the code so that it could avoid this

The general problem is that you are using the output array elements to hold two separate pieces of information: a not-set-yet flag, and the new value. To do this, the not-set-flag value has to be a value that won't occur in the input array.

If that isn't possible, the algorithm can't work. (You need an extra data structure for the not-set-yet flags.) If it is possible, you need to pre-initialize the output array with the not-set-yet value.
[ September 20, 2005: Message edited by: Kym Thompson ]