Randomly split sorted array into smaller sorted arrays

user_8321904 0
Viewed 85

I have a big sorted array of unique numbers. I do want to split it into n smaller disjoint sorted arrays with unique values. For example, I have an array [1, 2, 3, 4, 5, 6, 7, 8, 9] and the algorithm I am looking for gives one of the following results (n=3):

  1. [1, 4, 7], [5, 6, 9], [2, 3, 8]

  2. [3, 8, 9], [1, 5, 7], [2, 4, 6]

  3. [3, 4, 7], [1, 5, 8], [2, 6, 9], etc

Why I need it: I have a very big array (about 1 billion values) and I need to distribute values randomly between nodes in a simulated network, which together compute some aggregated value. They work more efficiently if they have sorted values. Since I am testing this system I need to run the simulation many times with the different amount of nodes, network topology, etc. Obviously simply splitting the data into several consecutive chunks is not suitable here.

sorting arrays algorithm
2 Answers

Create n smaller arrays and an array of n indices. There is one index for each of the small arrays; they are all initialized to zero. Iterate over the large sorted array, at each step choosing one of the small arrays to put the value into. If the small array is already 'full' (its index is already equal to the length of the array), pick the next small array that is not yet full. Insert the value from the large array into the small array at the current value of its index, and then increment the index.

This will require a fast random number generator and perhaps a clever way of taking the completed subarrays out of the rotation, but it is linear in the large sorted array and requires no sorting.

In Java a two-dimensional array is an array of arrays, and we can leverage that to alter which subarrays each row is pointing to on the fly. The idea here is that subarrays is an array containing all the subarrays, and the references to them never change, but candidate starts out with references to all of them and gradually adjusts itself so that only the arrays that are still not full are referenced.

int[][] splitSorted(int[] array, int n) {
    if (array.length % n != 0) {
        throw new IllegalArgumentException(
            n + " does not divide " + array.length + " evenly");
    }
    int size = array.length / n;  // size of each subarray
    int[][] subarrays = new int[n][size];
    int[][] candidate = Arrays.copyOf(subarrays, subarrays.length);
    int[] index = new int[n];

    Random rand = new Random();
    for (int i : array) {
        int which = rand.nextInt(n);
        candidate[which][index[which]] = i;  // insert into a subarray
        ++index[which];
        if (index[which] == size) {  // one has maxed out
            --n;  // remove it from consideration
            candidate[which] = candidate[n];
            index[which] = index[n];
        }
    }
    return subarrays;
}

When an array is full, we swap the one at the end of candidate into its place, so that the first rows contain the ones we're still trying to fill. Note that candidate completely loses track of the filled arrays. That's fine because they're still referenced by subarrays, which never changes. (We avoid having it alias candidate by taking a shallow copy with Arrays::copyOf when we create candidate.) We also have to swap the index for the array we're swapping.

Note also that the on the two lines that do the swap, which and n could be identical. An if could avoid setting them in this case, but setting them is redundant, so I prefer to keep the code simpler. n is decremented so the next time around the loop, we will pick a random number in a smaller range; only arrays that still need to be filled are considered. Finally, we return an array of all the filled subarrays.

It should be clear, but I will just underscore that because we put each value from the original large sorted array into one and only one subarray, and because we put them there in order, that the uniqueness and sorted constraints of the original array will be maintained on the subarrays.

user_6360090

You can shuffle the list, split into chunks and the sort the chunks. For example (solution in Python):

import random

n = 3
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]

random.shuffle(lst)

for i in range(0, len(lst), n):
    print(sorted(lst[i : i + n]))

Prints:

[1, 2, 8]
[3, 6, 9]
[4, 5, 7]
user_100359850
Related