Sorting 10,000 unique randomly-generated numbers I have to write this program in java.


  Write a program name sorting.java that will use an array to store 10,000 randomly generated numbers (ranging from 1 to 10,000 no repeat number).


Here is what I have so far:

public class Sort
{
    public static void main(String[] args)
    {


        Random rgen = new Random();  // Random number generator
        int[] nums = new int[10,000];  //array to store 10000 random integers (1-10,000)

        //--- Initialize the array to the ints 1-10,000
        for (int i=0; i&lt;nums.length; i++) {
            nums[i] = i;
        }

        //--- Shuffle by exchanging each element randomly
        for (int i=0; i&lt;nums.length; i++) {
            int randomPosition = rgen.nextInt(nums.length);
            int temp = nums[i];
            nums[i] = nums[randomPosition];
            nums[randomPosition] = temp;
        }

        //Print results
        for (int i = 0; i &lt; nums.length; i++){
        System.out.println(nums[i]);
        System.out.println("\n");
    }
}
Apart from the compiler errors, implementation issues and code style suggestions others have pointed out, your shuffling algorithm is fundamentally flawed.

Wikipedia explains it nicely:


  Similarly, always selecting i from the entire range of valid array
  indices on every iteration also produces a result which is biased,
  albeit less obviously so. This can be seen from the fact that doing so
  yields nn distinct possible sequences of swaps, whereas there are only
  n! possible permutations of an n-element array. Since nn can never be
  evenly divisible by n! when n > 2 (as the latter is divisible by n−1,
  which shares no prime factors with n), some permutations must be
  produced by more of the nn sequences of swaps than others. As a
  concrete example of this bias, observe the distribution of possible
  outcomes of shuffling a three-element array [1, 2, 3]. There are 6
  possible permutations of this array (3! = 6), but the algorithm
  produces 27 possible shuffles (33 = 27). In this case, [1, 2, 3], [3,
  1, 2], and [3, 2, 1] each result from 4 of the 27 shuffles, while each
  of the remaining 3 permutations occurs in 5 of the 27 shuffles.


To demonstrate this bias, I changed your code to only create three elements per array and ran it sixty million times. Here are the results:

Permutation    Occurences 
[1, 2, 3]:     8884128
[2, 3, 1]:     11111352
[3, 1, 2]:     8895318
[3, 2, 1]:     8891062
[2, 1, 3]:     11107744
[1, 3, 2]:     11110396


If your shuffling algorithm were correct, one would expect a relatively uniform distribution. However, the standard deviation is huge at about 1215764 (or ~2%) which should ring alarm bells. For comparison, here are the results of using the proven Fisher–Yates shuffle:

Permutation    Occurences 
[1, 2, 3]:     10000566
[2, 3, 1]:     9998971
[3, 1, 2]:     10000640
[3, 2, 1]:     10000873
[2, 1, 3]:     9998249
[1, 3, 2]:     10000701


As one would expect from a correct implementation, the standard deviation is low at about 1105 (or ~0.002%).

Here's the correct implementation for reference:

for (int i = numbers.length - 1; i &gt; 0; i--)
{
    int swapIndex = random.nextInt(i + 1);
    int temp = numbers[i];
    numbers[i] = numbers[swapIndex];
    numbers[swapIndex] = temp;
}


However, another problem presents itself even with a correct shuffling algorithm: 

A pseudo-random number generator is limited by its period, i.e. it can only produce a certain number of unique shuffles:


  [...] a shuffle driven by such a generator cannot possibly produce more distinct permutations than the generator has distinct possible states.


java.util.Random has a period no larger than 248 which is unable to produce an overwhelming majority of the 10000! (approximately 2.85 × 1035659) possible permutations of your array. The default implementation of SecureRandom isn't much better at no more than 2160. 

In the case of such a long array, the Mersenne Twister is a more adequate choice with a period of 219937-1 and excellently uniform distribution (although still not enough to produce all the possible permutations. At some point, it makes more sense to look into true random number generators that are based on physical phenomena). 

So, in my opinion, the real moral of the story is this:


  Take special care when working with randomness or pseudorandomness as the consequences of tiny mistakes can be hard to detect but devastating. Use Collections.shuffle instead of reinventing the wheel. For your (presumably) casual use, you might not need to worry about these inadequacies at all. On the other hand, it doesn't hurt to be aware of them.