Java: Randomly sort values in a array (the generic way) in single pass

Few years back (yes, about 4 years back), I wrote an article about randomly sort query results in MySQL. The main problem in randomly sort query results is that when you have a very large data in your database and the statement to sort the result may change the data execution plan causing DMBS does not choose the right plan. Therefore, sometime it is more wise to sort it in your own program instead of too depending on DBMS’s decision which may affect the overall performance of a program.

Instead of sorting the result in SQL statement, you can do it the programatic way. The pseudocode is as the following:

Load the results into an array
for each element in the array
  calculate a random number with index range from 0 to array size -1
  store the current element in a temporary variable
  replace the current element in the array with the element at the random index just now
  replace the element at random index with the element at temporary variable
end for

The code in Java programming language:

import java.util.Random;

public class SortUtil {
    public static  void sort(K[] values) {
        int i;
        int rand;
        K temp;
        Random random;

        random = new Random(System.currentTimeMillis());
        for (i = 0; i < values.length; i++) {
            rand = (random.nextInt() & 0x7FFFFFFF) % values.length;
            temp = values[i];
            values[i] = values[rand];
            values[rand] = temp;
        }
    }
}

To test the function:

...
    public static void main(String[] args) {
        Integer[] test = { 1, 2, 3, 4, 5, 6, 7, 8 , 9, 0 };

        SortUtil.sort(test);
        for(Integer i: test) {
            System.out.println("i = " + i.toString());
        }
    }
...

Leave a Reply