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<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");
}
}

• I would like to thank everyone as all your post have been excellent. – Fernando Martinez Apr 14 '13 at 21:50
• Three remarks: 1) Sort is just the opposite of Shuffle, which is what you should have named the class. 2) The comma in new int[10,000] is illegal syntax. 3) Your braces don't match. – 200_success Apr 13 '14 at 5:31

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 > 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.

You can simplify you shuffle like this:

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


This will replace the complete for loop.

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 }

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.