Advanced sorting / re-sorting arrays in Java

Question

So, I have an array with the following theoretical values:

int[] elements = {A1, A2, B1, B2, A3, A4, B3, B4, C1, C2, D1, D2, C3, C4, D3, D4}; 

Illustrative drawing:

  + - + - + - + - + | A | A | B | B | + - + - + - + - + | A | A | B | B | + - + - + - + - + | C | C | D | D | + - + - + - + - + | C | C | D | D | + - + - + - + - + 

Simply put, I would like the array to be reordered in the following form:

 int[] elements = {A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, D4}; 

Illustrative drawing:

  + - + - + - + - + | A | A | A | A | + - + - + - + - + | B | B | B | B | + - + - + - + - + | C | C | C | C | + - + - + - + - + | D | D | D | D | + - + - + - + - + 

This specific example contains four sectors (A, B, C and D), but the required algorithm should work, despite the many or more sectors that the array contains, and no matter how many elements in each sector.

The known size of each sector (sector width and sector height), as well as the number of sectors (rows and columns). All sectors have the same size (width and height). The number of sectors should be described as two values ​​(ans columns), which are then multiplied by the actual amount of sectors. For instance. if 5 sectors are required, then 1 row and 5 columns can be specified.

The following is an example of how the method that precedes this view looks like:

 public int[] sectorSort(int[] elements, int sectorWidth, int sectorHeight, int columns, int rows); 

Example settings for another sector:

  Columns: 5 + - + - + - + - + - + - + - + - + - + - + | A | A | B | B | C | C | D | D | E | E | Rows: 1 + - + - + - + - + - + - + - + - + - + - + | A | A | B | B | C | C | D | D | E | E | + - + - + - + - + - + - + - + - + - + - + Columns: 2 + - + - + - + - + | A | A | B | B | + - + - + - + - + | A | A | B | B | + - + - + - + - + | C | C | D | D | Rows: 3 + - + - + - + - + | C | C | D | D | + - + - + - + - + | E | E | F | F | + - + - + - + - + | E | E | F | F | + - + - + - + - + 

I plan to use this to create an efficient sprite map class for the game engine that I make. The elements of the array are ARGB color values, and the sectors are individual sprites. If the various orders are ordered in the last order, then the search for individual sprites is much faster, and the memory efficiency.

Thanks!

EDIT1: Clarity.

EDIT2: added additional conditions and clarifications.

Answer 1

You will not get more complicated time complexity than this: It creates a new array and copies every sector into it.

 static T[] sectorSort<T>(T[] elements, int sectorWidth, int sectorHeight, int columns, int rows) { T[] sortedElements = new T[elements.Length]; int n = 0; int arrWidth = sectorWidth * columns; for(int secY = 0; secY < rows; secY++) for (int secX = 0; secX < columns; secX++) { int baseIndex = secY * arrWidth * sectorHeight + secX * sectorWidth; for(int y = 0; y < sectorHeight; y++) for (int x = 0; x < sectorWidth; x++) { int sourceIndex = baseIndex + y * arrWidth + x; sortedElements[n++] = elements[sourceIndex]; } } return sortedElements; } 

I still see a lot of optimizations that can be performed, but, reading your question, I see that this is done at boot time, so don't worry too much about it.

EDIT: fixed code

EDIT2: test setup (C #)

  int[] array = new int[] { 11, 12, 13, 21, 22, 23, 51, 52, 53, 14, 15, 16, 24, 25, 26, 54, 55, 56, 17, 18, 19, 27, 28, 29, 57, 58, 59, 31, 32, 33, 41, 42, 43, 61, 62, 63, 34, 35, 36, 44, 45, 46, 64, 65, 66, 37, 38, 39, 47, 48, 49, 67, 68, 69, 71, 72, 73, 81, 82, 83, 91, 92, 93, 74, 75, 76, 84, 85, 86, 94, 95, 96, 77, 78, 79, 87, 88, 89, 97, 98, 99, }; int[] sorted = sectorSort(array, 3, 3, 3, 3); for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) Console.Write(sorted[x + y * 9] + " | "); Console.WriteLine("\n"); } 

Answer 2

You can execute a direct algorithm that iterates over all sectors and all elements in them to change them. This will be O (n * m), n = number of sectors and m = number of elements per sector. But you have to rebuild the whole array. Alternatively (if memory is important), you can create a sector view of the original array, which will require O (n) to create the view, and then O (m) to read the values ​​of one sector.

Thus, reading all sectors will require O (n * m) in both cases. What improvement do you expect?