Sorting 10,000 unique randomly-generated numbers

Question

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<nums.length; i++) {
            nums[i] = i;
        }

        //--- Shuffle by exchanging each element randomly
        for (int i=0; i<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 < nums.length; i++){
        System.out.println(nums[i]);
        System.out.println("\n");
    }
}

Answer 1

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 nⁿ distinct possible sequences of swaps, whereas there are only n! possible permutations of an n-element array. Since nⁿ 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 nⁿ 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 (3³ = 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 > 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 2⁴⁸ which is unable to produce an overwhelming majority of the 10000! (approximately 2.85 × 10³⁵⁶⁵⁹) possible permutations of your array. The default implementation of SecureRandom isn't much better at no more than 2¹⁶⁰.

In the case of such a long array, the Mersenne Twister is a more adequate choice with a period of 2¹⁹⁹³⁷-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.

Answer 2

You can simplify you shuffle like this:

Collections.shuffle(Arrays.asList(nums));

This will replace the complete for loop.

Answer 3

Nearly right.

List item

You want:

for (int i=0; i<nums.length; i++) {
    nums[i] = i + 1;
}

or you'll get 0-9,999, the question says 1-10,000

Also, the print loop is missing a closing }

Answer 4

To add to what others have said so far

One small thing about coding style!

Try to keep your variable names as consistent as possible.

randomPosition versus rgen

If you choose to use full words in camelCase, try keeping the same style everywhere.

So rgen should be change to something, at least like rGen, but even better to randomGenerator. Also the variable nums should be change to numbers.

This will keep the code cleaner and increases readability.