Java 2d array sort merge to 1d

Question

I have one sorted 2dimensional array (the rows are in ascending order). I want to transform it to one sorted 1dimensional array to use it in one of my functions. How can I do it?

Thanks for the help!

Answer 1

The easiest way will be to:

1. Count the total number of elements
2. Allocate a new array
3. Loop through the arrays adding them to the new one
4. Use Arrays.sort() on the result.

You may be able to use the fact the arrays are already sorted to try and do something fancy with insertion but the performance gains will be small and the increase in code complexity will be massive. You are far more likely to add bugs than to gain performance.

To do the sorted insertion you would need an array of indexes for each source array.

1. Count the total number of elements
2. Allocate a new array
3. Loop through all the arrays and find the one with the lowest (or highest depending on sort direction) value
4. Insert that value and increment the index for that source array and for the destination array by one.
5. Go back to step 3 until you run out of data in all the source arrays

Answer 2

Assuming that the subarrays have the same length and that the first element of each row is no less than the last element of the previous row:

Object[][] twoDArray;
// you are initializing it with some code here
int len = 0;
for (Object[] x : twoDArray) {
    len += x.length;
}
Object[] oneDArray = new Object[len];
for (int i=0; i<len; ++i) {
    oneDArray[i] = twoDArray[i/twoDArray.length][i%twoDArray.length];
}

This has O(n + m) complexity.

If my second assumption is faulty (as you seem to indicate in your comments), then you should call Arrays.sort on your final array. The final complexity will be O(n + m + nlogn).

It is almost certain that you cannot optimize your sorting more than this. Sorting in the middle of your array conversion will require another full iteration per sub-iteration, in order to insert the element from the next row in its proper location and then move each element ahead of it up one index.

Answer 3

Just loop through the 2D array and assign the values into a 1D array.

Answer 4

Assuming your bidimensional array is R Rows and C columns. You can

1. Create a monodimensional array with R x C as size.
2. Use R indexes, one for each row and insert (in a loop) in your monodimensional array the minor of your values in each iteration (just be careful once you fetched an entire row. This must be managed)

In the end, you should have a monodimensional array with all elements already sorted without further operations.