Randomly generating a sorted array

Question

I'm writing a method that generates a random integer array that are sorted. It takes the arguments of min value, max value and the length of desired array. So for example the arguments with min val = 1 max val = 10 length = 5 could give [1,1,2,3,5,6,9,9,9,10] or [2,4,5,6,6,6,6,6,6,8]. Let me know if the specifications are unclear and I'll elaborate.

Here is my code; it works but is a bit messy:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.ListIterator;
import java.util.Random;

public class test {
    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(generateSorted(10, 0, 100)));
    }

    public static int[] generateSorted(final int length, final int minVal, final int maxVal)
    {
        ArrayList<Integer> data = new ArrayList<>(length);
        data.add(getRandomVal(minVal, maxVal));

        boolean added;
        for(int i = 0; i < length; i++)
        {
            added = false;
            ListIterator<Integer> itr = data.listIterator();
            int rndNum = getRandomVal(minVal, maxVal);
            while(itr.hasNext() && !added)
            {
                Integer currentNum = itr.next();
                if(currentNum >= rndNum)
                {
                    itr.previous();
                    itr.add(rndNum);
                    added = true;
                }
            }

            if(!added)//add to end of arrayList
            {
                data.add(rndNum);
            }
            //printArrList(data);
        }

        return data.stream().mapToInt(i -> {
            return i;
        }).toArray();
    }

    /*prints contents of arraylist all on 1 line*/
    public static void printArrList(ArrayList<Integer> al)
    {
        System.out.print("[");
        /*this could be replaced with a for (each) loop*/
        al.stream().forEach((i) -> {
            System.out.print(i+", ");
        });
        System.out.println("]");
    }

    /*returns random int between [min, max]*/
    private static int getRandomVal(int min, int max)
    {
        int n = max - min + 1;
        int i = rand.nextInt(n);//nextInt(n) returns random int in [0, n)
        return min + i;
    }
    final static private Random rand = new Random();
}

Answer 1

In generateSorted, in every iteration of the outer for loop, you walk over the data array elements until you find the right position to insert. In the worst case, this could be very inefficient. You can improve the performance using binary search:

public int[] generateSorted(final int length, final int minVal, final int maxVal) {
    List<Integer> data = new ArrayList<>(length);

    for (int i = 0; i < length; i++) {
        int rndNum = getRandomVal(minVal, maxVal);
        int insertionPoint = Collections.binarySearch(data, rndNum);
        data.add(insertionPoint > -1 ? insertionPoint : - insertionPoint - 1, rndNum);
    }

    return data.stream().mapToInt(i -> i).toArray();
}

Some other improvements I did here:

• Changed i -> { return i; } to the lambda expression i -> i
• Generate an array of length, instead of length + 1 as your version
• Declare data as List instead of ArrayList

I would also shorten getRandomVal like this:

private int getRandomVal(int min, int max) {
    return min + rand.nextInt(max - min + 1);
}

Finally, I would make the whole thing testable, something like this:

class GenRandomArray {

    private final Random rand;

    public GenRandomArray() {
        rand = new Random();
    }

    public GenRandomArray(int seed) {
        rand = new Random(seed);
    }

    public int[] generateSorted(final int length, final int minVal, final int maxVal) {
        List<Integer> data = new ArrayList<>(length);

        for (int i = 0; i < length; i++) {
            int rndNum = getRandomVal(minVal, maxVal);
            int insertionPoint = Collections.binarySearch(data, rndNum);
            data.add(insertionPoint > -1 ? insertionPoint : -insertionPoint - 1, rndNum);
        }

        return data.stream().mapToInt(i -> i).toArray();
    }

    private int getRandomVal(int min, int max) {
        return min + rand.nextInt(max - min + 1);
    }
}

public class GenRandomArrayTest {
    @Test
    public void testGen10_Between_0_and_100() {
        assertArrayEquals(new int[]{5, 9, 42, 54, 67, 72, 82, 84, 93, 98},
                new GenRandomArray(0).generateSorted(10, 0, 100));
    }
}

About Collections.binarySearch

The javadoc says:

returns: the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

If the value is greater than -1, it's the index of the item we searched for. In other words the random number we generated is already in the list. We can insert it this duplicate right there.

If the value is -1 or smaller, the item is not yet in the list, and the returned \$x\$ is such that \$-x - 1\$ is the right place to insert the item to keep the elements ordered.

It becomes clearer to see if you print out the random number, the returned \$x\$ and the content of the list, for example when using \$seed = 0\$ and \$(10, 0, 10)\$ as the params of the generator:

0 : -1 : []
6 : -2 : [0]
8 : -3 : [0, 6]
5 : -2 : [0, 6, 8]
6 : 2 : [0, 5, 6, 8]
2 : -2 : [0, 5, 6, 6, 8]
2 : 1 : [0, 2, 5, 6, 6, 8]
6 : 5 : [0, 2, 2, 5, 6, 6, 8]
2 : 1 : [0, 2, 2, 5, 6, 6, 6, 8]
0 : 0 : [0, 2, 2, 2, 5, 6, 6, 6, 8]

For example:

• When inserting 8, it doesn't exist in the list, the returned \$x = -3\$, so we should insert at position \$-x -1 = 3 - 1 = 2\$.
• When inserting 2 for the second time, the returned \$x = 1\$, so we should insert at position 2.

Conclusion

It's not worth trying to keep the list sorted. The binary search makes it faster than the original implementation, but keep in mind that the insertion is costly, as every time you insert something, the rest of the array has to be copied. And you cannot compensate for that by using LinkedList instead of ArrayList, because efficient binary search requires a random access list, with a LinkedList you would lose efficiency due to the traversal of elements.

Overall, this will be slower than first adding all the elements and then later sorting with Arrays.sort. So do it that way instead.

public int[] generateSorted(final int length, final int minVal, final int maxVal) {
    List<Integer> data = new ArrayList<>(length);

    for (int i = 0; i < length; i++) {
        data.add(getRandomVal(minVal, maxVal));
    }
    Collections.sort(data);

    return data.stream().mapToInt(i -> i).toArray();
}

Answer 2

Currently there are two answers to this question, and I am not happy that either solution is ideal.

The initial question has a method with the signature:

public static int[] generateSorted(final int length, final int minVal, final int maxVal)

This is what I would consider a great method signature. It uses Java primitives, has final arguments, and a good name.

What's missing is a specification of whether the maxVal is inclusive, or exclusive. The code and examples make it clear that the maxVal is inclusive. This should be carefully documented in the JavaDoc for the final method.

The guts of the method are all messy, though. My primary beef is that you resort to using Integer objects, instead of int primitives.

If you were to keep this process simple, it would also be a whole lot faster.

Consider guts that look like:

final int randlimit = maxVal - minVal + 1;
final int[] result = new int[length];
for (int i = 0; i < length; i++) {
    result[i] = minVal + rand.nextInt(randLimit);
}
Arrays.sort(result);
return result;

The advantage of this, is that:

• it is a true \$O(n \log(n))\$ operation. This is about as efficient as you can get.
• there is no autoboxing
• the logic is simple

Answer 3

private static Random rand = new Random();

public static void main(String[] args) {
    System.out.println(Arrays.toString(generateSorted(10, 0, 100)));
}

public static Object[] generateSorted(final int length, final int minVal,
        final int maxVal) {
    List<Integer> unsortedList=getUnSortedList(length,minVal,maxVal);
    Collections.sort(unsortedList );
    return unsortedList.toArray();

}

private static List<Integer> getUnSortedList(final int length, final int minVal,
        final int maxVal) {
    List<Integer> list=new ArrayList<Integer>();
    for(int i=0;i<length;i++){
        //creates a random number from 0 ~ max value exclusive, then add the min value.
        list.add(rand.nextInt(maxVal)+minVal);
    }
    return list;

}

First create the list then sort it. If you try to sort it while you create it you might be doing more operations then you will need to do in worse case.

Answer 4

If the minVal and maxVal are reasonably close you can use accumulation to do away with the sorting completely. Simply accumulate the number of times each value is randomly generated then create the results array in order.

public static int[] generateSorted(final int length, final int minVal, final int maxVal) {
   int span = maxVal - minVal + 1;
   int[] accumulator = new int[span];
   for(int genIdx = 0; genIdx < length; genIdx++) {
      accumulator[rand.nextInt(span)]++;
   }
   int resultIdx = 0;
   int[] result = new int[length];
   for(int accIdx = 0; accIdx < span; accIdx++) {
      for(int valIdx = 0; valIdx < accumulator[accIdx]; valIdx++) {
         result[resultIdx++] = accIdx + minVal;
      }
   }
   return result;
}

It's an O(n) algorithm for moderate spans. If you need to support larger spans or all ints you could have a splitting function that uses this if the span is under a K or two then uses either of the other answers for larger spans.

Answer 5

If the number of possible values is not too large compared with the length of the list, you could make an array r indexed from 0 to max_val - min_val, initializing every entry to zero. Then generate length random values in the range 0 to max_val - min_val. For each random value, if the value is k, then increment r[k] by 1.

Once you have generated all the random values, you can read off the entries of your final result from the value in the array r. For each k from 0 to max_val - min_val, append r[k] copies of min_val + k to your final result.

The running time of this is \$O(\max(m,n))\$ where \$m\$ is the number of possible values (max_val - min_val + 1) and \$n\$ is the number of values in your output (length). This is not as good as \$O(n \log n)\$ if \$m\$ can grow faster than \$\log n\$, but it scales nicely to large values of \$n\$ if \$m\$ is constant or slowly growing.

An alternative approach is to generate the \$k\$th order statistic of your distribution, one element at a time from \$k = 1\$ to \$k =\$ length. No sorting is required, because the elements are generated in the final sequence, but this algorithm requires knowing the distribution of the \$k\$th order statistic given the value of the \$k-1\$st order statistic. For a set of uniform continuous iid variables the distribution of the 1st order statistic is a beta distribution, and I think the remaining conditional distributions are also beta distributions; to get a discrete distribution I think you could generate your output as if it were for a uniform continuous distribution from min_val - 1 to max_val, and at the end round all the results up to the next integer. But the validity of this approach would probably be better to question on https://math.stackexchange.com/.