Sorting a list into multiple vertical columns

Question

Does anyone have a good algorithm for re-sorting an array of values (already pre-sorted) so that they can be displayed in multiple (N) columns and be read vertically? This would be implemented in .Net but I'd prefer something portable and not some magic function.

A good example of it working is the ASP.Net CheckBoxList control rendering as a table with the direction set to vertical.

Here's an example of the input and output:

Input:

Columns = 4
Array = {"A", "B", "C", "D", "E", "F", "G"}

Output:

ACEG
BDF

Thanks!

Updated (More Info):

I think I might have to give a little more information on what I'm trying to do... Mostly this problem came about from going from using a CheckBoxList's automatic binding (where you can specify the columns and direction to output and it would output a table of items in the correct order) to using jQuery/AJAX to create the checkbox grid. So I'm trying to duplicate that layout using css with div blocks with specified widths (inside a container div of a known width) so they wrap after N items (or columns.) This could also be rendered in a table (like how ASP.Net does it.)

Everything works great except the order is horizontal and when you get a large number of items in the list it's easier to read vertical columns.

If the array doesn't have enough items in it to make an even grid then it should output an empty spot in the correct row/column of the grid.

And if an array doesn't have enough items to make even a single row then just output the items in their original order in one row.

Some other input/ouput might be:

Columns = 3
Array = {"A", "B", "C", "D"}

ACD
B

Columns = 5
Array = {"A", "B", "C", "D", "E", "F", "G", "H"}

ACEGH
BDF

Columns = 5
Array = {"A", "B", "C", "D"}

ABCD

Answer 1

Okay, I'm sorry for my initial statement, but when you want it to work as you described in the comment to my first answer, you need in fact re-sort the data... well somewhat. It could maybe be done without the helper matrix, however the resulting code is probably very complex and as long as the matrix will only use a couple of bytes of memory, why not using this little helper construct?

What my code does below is creating a matrix. We write the matrix from top to bottom and then from left to right (and stop filling up anything but the first row when we run out of elements to fill up all columns of the first row). Then we read it in a different order, left to right and top to bottom. Basically what we do here is transposing a matrix, by writing it in one order, but reading it in another order. Transposing a matrix is a very elementary mathematical operation (lots of 3D programming works by using matrix calculations and transposing is actually a simple operation). The trick is how we initially fill up the matrix. To make sure we can fill up the first column in any case, independently of number of desired columns and size of the array, we must stop filling the matrix in the normal order if we run out of elements and reserve all elements left over for the first row. This will produce the output you have suggested in your comment.

The whole thing is bit complicated to be honest, but the theory behind it should be sane and it works lovely :-D

int Columns;
char * Array[] = {"A", "B", "C", "D", "E", "F", "G"};

int main (
    int argc,
    char ** argv
) {
    // Lets thest this with all Column sizes from 1 to 7
    for (Columns = 1; Columns <= 7; Columns++) {

        printf("Output when Columns is set to %d\n", Columns);

        // This is hacky C for quickly get the number of entries
        // in a static array, where size is known at compile time
        int arraySize = sizeof(Array) / sizeof(Array[0]);

        // How many rows we will have
        int rows = arraySize / Columns;

        // Below code is the same as (arraySize % Columns != 0), but
        // it's almost always faster
        if (Columns * rows != arraySize) {
            // We might have lost one row by implicit rounding
            // performed for integer division
            rows++;
        }

        // Now we create a matrix large enough for rows * Columns
        // references. Note that this array could be larger than arraySize!
        char ** matrix = malloc(sizeof(char *) * rows * Columns);

        // Something you only need in C, C# and Java do this automatically:
        // Set all elements in the matrix to NULL(null) references
        memset(matrix, 0, sizeof(char *) * rows * Columns );

        // We fill up the matrix from top to bottom and then from
        // left to right; the order how we fill it up is very important
        int matrixX;
        int matrixY;
        int index = 0;
        for (matrixX = 0; matrixX < Columns; matrixX++) {
            for (matrixY = 0; matrixY < rows; matrixY++) {
                // In case we just have enough elements left to only
                // fill up the first row of the matrix and we are not
                // in this first row, do nothing.
                if (arraySize + matrixX + 1 - (index + Columns) == 0 &&
                        matrixY != 0) {
                    continue;
                }

                // We just copy the next element normally
                matrix[matrixY + matrixX * rows] = Array[index];
                index++;
                //arraySize--;
            }
        }

        // Print the matrix exactly like you'd expect a matrix to be
        // printed to screen, that is from left to right and top to bottom;
        // Note: That is not the order how we have written it,
        // watch the order of the for-loops!
        for (matrixY = 0; matrixY < rows; matrixY++) {
            for (matrixX = 0; matrixX < Columns; matrixX++) {
                // Skip over unset references
                if (matrix[matrixY + matrixX * rows] == NULL)
                    continue;

                printf("%s", matrix[matrixY + matrixX * rows]);
            }
            // Next row in output
            printf("\n");
        }
        printf("\n");

        // Free up unused memory
        free(matrix);
    }   
    return 0;
}

Output is

Output when Columns is set to 1
A
B
C
D
E
F
G

Output when Columns is set to 2
AE
BF
CG
D

Output when Columns is set to 3
ADG
BE
CF

Output when Columns is set to 4
ACEG
BDF

Output when Columns is set to 5
ACEFG
BD

Output when Columns is set to 6
ACDEFG
B

Output when Columns is set to 7
ABCDEFG

This C code should be easy to port to PHP, C#, Java, etc., there's no big magic involved, so it's pretty much universal, portable and cross-platform.

---

One important thing I should add:

This code will crash if you set Columns to zero (division by zero, I don't check for that), but what sense would 0 Columns make? And it will also crash if you have more columns than elements in the array, I don't check for this either. You can easily check for either right after you got the arraySize:

if (Columns <= 0) {
   // Having no column make no sense, we need at least one!
   Columns = 1;
} else if (Columns > arraySize) {
   // We can't have more columns than elements in the array!
   Columns = arraySize;
}

Further you should also check for the arraySize being 0, in which case you can jump out straight away of the function, as in that case there is absolutely nothing to do for the function :) Adding these checks should make the code rock solid.

Having NULL Elements in the Array will work, BTW, in that case there are no holes in the resulting output. NULL elements are just skipped like not being present. E.g. lets use

char * Array[] = {"A", "B", "C", "D", "E", NULL, "F", "G", "H", "I"};

The output will be

ADFI
BEG
CH

for Columns == 4. If you want holes, you need to create a hole element.

char hole = 0;
char * Array[] = {"A", "B", &hole, "C", "D", "E", &hole, "F", "G", "H", "I"};

and modify the painting code a bit

    for (matrixY = 0; matrixY < rows; matrixY++) {
        for (matrixX = 0; matrixX < Columns; matrixX++) {
            // Skip over unset references
            if (matrix[matrixY + matrixX * rows] == NULL)
                continue;

            if (matrix[matrixY + matrixX * rows] == &hole) {
                printf(" ");
            } else {
                printf("%s", matrix[matrixY + matrixX * rows]);
            }
        }
        // Next row in output
        printf("\n");
    }
    printf("\n");

Output samples:

Output when Columns is set to 2
A 
BF
 G
CH
DI
E

Output when Columns is set to 3
ADG
BEH
  I
CF

Output when Columns is set to 4
AC H
BDFI
 EG