Advanced array sorting / rearranging in Java
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};
Illustration:
+ - + - + - + - + | A | A | B | B | + - + - + - + - + | A | A | B | B | + - + - + - + - + | C | C | D | D | + - + - + - + - + | C | C | D | D | + - + - + - + - +
Simply put, I want to rearrange the array into the following form:
int[] elements = {A1,D4};
Illustration:
+ - + - + - + - + | A | A | A | A | + - + - + - + - + | B | B | B | B | + - + - + - + - + | C | C | C | C | + - + - + - + - + | D | D | D | D | + - + - + - + - +
This particular example contains four sectors (a, B, C and D), but the algorithm I need should work, but the array contains many or several sectors, and each sector contains many elements
The size of each sector is known (sector width and sector height) and the number of sectors (rows and columns) All sectors have the same size (width and height) The number of sectors must be described as two values (rows and columns) and multiplied by them to form the actual sum of sectors For example If you need 5 sectors, you can specify 1 row and 5 columns
The following is an example of a method of pre forming this class:
public int[] sectorSort(int[] elements,int sectorWidth,int sectorHeight,int columns,int rows);
Examples of other sector settings:
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'm going to use it to create an efficient elf map class for the game engine I'm making The elements in the array are ARGB color values, and the sectors are separate sprites If different sprites are arranged in the latter order, searching for a single sprite is much faster and memory efficiency will be improved
thank you!
Edit 1: clarity
Edit2: added more conditions and descriptions
Solution
You won't gain time complexity better than this:
static T[] sectorSort<T>(T[] elements,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 can still see a lot of optimizations that can be done, but reading your question, I see that this is done at load time, so don't exaggerate it
Editing: fixed codes
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); for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) Console.Write(sorted[x + y * 9] + " | "); Console.WriteLine("\n"); }