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

Answer 2

A small UPDATE:

The algorithm I'm using here is a modified one you'd use for painting images. I'm pretending the array entries to be pixel data of an image and then I'm painting the image from left to right (1. LtoR) and from top to bottom (2. TtoB), however, the image data is stored from top to bottom (1. TtoB) and then from left to right (2. LtoR); IOW in a different order. Since an image can't have holes, this is the reason why it will not work with 5 or 6 columns. With 4 columns the output is

ACEG
BDF

As an image this looks like this

OOOO
OOO.

With O being a pixel of the image and . being an undefined pixel (a missing one). Missing ones may only be at the end of the image, not in the middle of it. That means it could also look like this

OOO
OO.
OO.
OO.

All missing pixels are always at the end, if you read first from top to bottom and then from left to right, because in that case all missing pixels follow directly each other at the end. If I read the diagram TtoB and then LtoR, it must read like this "Pixel, Pixel, Pixel, Pixel, ..., Pixel, Missing, Missing, Missing, ..., Missing", it might never read "Pixel, Missing, Pixel" or "Missing, Pixel, Missing". All pixels are together and all missings are, too.

With 5 columns, as the comment suggests, it should look like this

ACEFG
BD

However, as image this would look like this

OOOOO
OO...

And this is not allowed by the algorithm. If I read it TtoB and then LtoR, it will read: "Pixel, Pixel, Pixel, Pixel, Pixel, Missing, Pixel, Missing, Pixel, Missing". And as stated above, this is not allowed by the algorithm. So this simple pixel painting approach will not paint as many columns as requested if painting that many columns leads to holes in the image. In that case it will simply fill up the holes, however, this will cause less columns to be drawn.

Let me think of a solution that will always paint the requested numbers of pixels (in a separate reply).

---

You don't have to re-arrange the data in memory for that at all. Just print it in the desired order.

Some C Code (I'm doing it extremely verbose, so everyone understands what I'm doing so. Of course this can be much more compact):

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

int main (
    int argc,
    char ** argv
) {
    // 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 are we going to paint?
    int rowsToPaint = (arraySize / Columns) + 1;

    int col;
    int row;

    for (row = 0; row < rowsToPaint; row++) {
        for (col = 0; col < Columns; col++) {
            int index = col * rowsToPaint + row;

            if (index >= arraySize) {
                // Out of bounds
                continue;
            }

            printf("%s", Array[index]);
        }
        printf("\n"); // next row
    }
    printf("\n");
    return 0;
}

Note: This works fine with a value of 8 (so everything is painted within one row) and values of 4 and below (works fine with 3, 2 and 1), but it can't work with 5. This is not the fault of the algorithm, it is the fault of the constrain.

ACEFG
BD

The constraint says the columns are read top to bottom to get the corrected sorted data. But above "EFG" is sorted and it's not top to bottom, it is left to right. Thus this algorithm has a problem. Using Columns = 3 will work

ADG
BE
CF

Using two will work as well

AE
BF
CG
D

And one will put everything into one column.

Answer 3

This looks like homework assignments anyway

array<String^>^  sArray = {"A", "B", "C", "D", "E", "F", "G"};
double Columns = 4;
double dRowCount = Convert::ToDouble(sArray->Length) / Columns;
int rowCount = (int) Math::Ceiling(dRowCount);
int i = 0;
int shift = 0;
int printed = 0;
while (printed < sArray->Length){
    while (i < sArray->Length){
        if (i % rowCount == shift){
            Console::Write(sArray[i]);
            printed++;
        }
        i++;
    }
    Console::Write("\n");
    i = 0;
    shift++;
}