Matrix Sorting mergesort C

I have this problem where I have to sort a matrix like:

to:

So rows stay the same, from smaller to bigger per columns as shown in the example. Matrix will always have 3 columns and x rows.

I already tried Insertion Sorting this and despite working it is not efficient and takes to much to run given the amount of rows in the real application.

I'll provide a small code of what I pretend:

#include <stdio.h>

int main() {
    int abc[6][3] = {
        { 0, 0, 4 },
        { 1, 0, 3 },
        { 0, 1, 4 },
        { 1, 1, 5 },
        { 0, 2, 3 },
        { 1, 2, 4 },
    };

    //
    //sort 
    //

    for (int i = 0; i < 6; ++i) {
        printf("%d %d %d\n", abc[i][0], abc[i][1], abc[i][2]);
    }
    return 0;
}

I'd like to try both mergesort and quicksort but any help is appreciated.

Thank You in advance.

Solution

You can approach writing your compare function in one of four ways (two formally proper, but all equivalent ¹). The scary qsort prototype int compare (const void *a, const void *b) is simply the way C has of passing a pointer to elements of the array to be sorted. Your job is simply to cast back to the correct type before comparing in the function.

The real question is "What type pointer is being passed?

When you answer that it's easy. You are sorting a 2D array by rows. A 2D array is actually an array of 1D arrays. Each pointer passed to compare will be a pointer to a 1D array (the rows)

So each a and b will be a pointer to array of int [3]. In your compare function, you will need to cast to a pointer to array of int [3] and then dereference once to leave the type as int [3] and then compare based on the third element. (but when you access your now type int [3] array pointer conversion applies to that array as well, so you simply need to add 2 to your pointer value and dereference to compare by the third element).

You can use the result of two conditional tests to avoid potential overflow which can result from simply returning b - a which if b is a large negative number and a is large (or b is a large positive number and a a large negative number) will occur if the result exceeds the storage capacity for int. So instead, for an ascending sort, you can use:

    return (a > b) - (a < b);

(for a descending sort, just turn the comparisons around, e.g. (a < b) - (a > b). Try it. Pick any two values for a and b and compute the result. In the ascending case is a is less than b, you return 0 - 1; (or -1), e.g. meaning a sorts before b)

So what does the compare function look like? Since the formal type for pointer to array of int [3] is int (*)[3], you can do:

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

or if you wanted to simply make int pa2 and not worry about having to dereference the pointer in the comparison, for the second formal cast you could enclose the complete cast of a in parenthesis and then just use the (stuff a)[2] to access the third integer value directly -- it just makes for a messier looking cast, e.g.

int comp (const void *a, const void *b)
{
    int pa2 = (*(int (*)[3])a)[2],
        pb2 = (*(int (*)[3])b)[2];

    return (pa2 > pb2) - (pa2 < pb2);
}

(whatever makes the most sense to you)

Then the sorting by the third element of each row in your 2D array is really trivial, e.g.

#include <stdio.h>
#include <stdlib.h>

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

int main() {

    int abc[6][3] ={{0,0,4},
                    {1,0,3},
                    {0,1,4},
                    {1,1,5},
                    {0,2,3},
                    {1,2,4}};

    qsort (abc, 6, sizeof *abc, comp);

    for (int i = 0; i < 6; ++i)
        printf(" %2d %2d %2d\n", abc[i][0], abc[i][1], abc[i][2]);

}

Example Use/Output

$ ./bin/qsort2d+2
  1  0  3
  0  2  3
  0  0  4
  0  1  4
  1  2  4
  1  1  5

Now the last two equivalent ways of writing the compare function casts rely on the successive application of array/pointer conversion and understanding that a pointer to array and the array itself will both point to the same address (but are formally of different types) Formally you have int (*)[3] but since you know you simply want the second integer after that address, you can cast the compare pointer a and b to int * and add two. This is equivalent, but does not reflect the formal cast. (you can also enclose the whole cast in parenthesis and use [2] as well).

The casts look much simpler in that case, but it can be somewhat less apparent what is actually taking place. I'll leave it to you to try replacing *(int (*)[3]) in the complete program with (int *). (that will avoid the protracted discussion that will take place in the comments)

Look things over and think through both "What type pointer is being passed?" and why use the result of two comparisons instead of just the subtraction as the return in your compare function to avoid overflow. Let me know if you have any further questions.

Footnotes:

1.) C11 Standard - 6.3.2.1 Other Operands - Lvalues, arrays, and function designators(p3) Except when it is the operand of the sizeof operator, the _Alignof operator, or the unary '&' operator, or is a string literal used to initialize an array, an expression that has type "array of type" is converted to an expression with type "pointer to type" that points to the initial element of the array object and is not an lvalue.