patternjavaMinor

Randomly generating a sorted array

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

sortedrandomlygeneratingarray

Problem

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 data = new ArrayList<>(length);
data.add(getRandomVal(minVal, maxVal));

boolean added;
for(int i = 0; i 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 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

Solution

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 data = new ArrayList<>(length);

    for (int i = 0; i  -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 data = new ArrayList<>(length);

        for (int i = 0; i  -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 data = new ArrayList<>(length);

    for (int i = 0; i  i).toArray();
}

Code Snippets

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

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

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]

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

Context

StackExchange Code Review Q#60067, answer score: 4

Revisions (0)

No revisions yet.