Sorting a 2 Dimensional Array by First Dimension (C)

Question

I have a 2 dimensional array that I am trying to sort in ascending order. For example, say the array looks like this:

4, 5
2, 6
7, 2
8, 4

I would like it to look like this:

2, 6
4, 5
7, 2
8, 4

The code that I have so far:

int temp = 0;
for(int m = 0; m<=nonZeroLength-1; m++){
    for(int n = m+1; n<=nonZeroLength-1; n++){
        if(nonZeroScoreSorcting[m] > nonZeroScoreSorcting[m+1]){
            temp = nonZeroScoreSorcting[m];
            strcpy(nonZeroScoreSorcting[m], nonZeroScoreSorcting[n]);
            strcpy(nonZeroScoreSorcting[n], temp);
        }
    }
}

Assume that nonZeroLength has a value of 4 for this example. I am using strcpy() because I read that that is the only way to change elements of an array in C. When I run the program I get the following error:

passing argument 1 of ‘strcpy’ from incompatible pointer type [-Wincompatible-pointer-types]

I have also tried the regular assign method:

if(nonZeroScoreSorcting[m] > nonZeroScoreSorcting[m+1]){
    temp = nonZeroScoreSorcting[m];
    nonZeroScoreSorcting[m] = nonZeroScoreSorcting[n];
    nonZeroScoreSorcting[n] = temp;
}

Answer 1

If you do in fact have a 2D array of int as you indicate, the key to sorting the array by row is understanding that during the sort, you will need to swap rows, not simply values. This is how you preserve the row-wise relationship during the sort.

You cannot do that treating each row of int as a string and attempting a row-wise copy using strcpy. This will result in Undefined Behavior when strcpy accesses values in the src argument outside the array bounds looking for a nul-terminating character that isn't present.

(though technically, providing a properly sized array for each src and dest and sizing 'n' in strncpy to copy 2 * sizeof(int) bytes can copy rows by virtue of limiting the read to n chars where no nul-terminating character is present -- but DON'T do it -- that's what memcpy (or memmove) is for).

Though the recommended way to sort in C is using the qsort function provided in stdlib.h, you can provide whatever sort algorithm you want. It will likely not be anywhere close to the efficiency of qsort, and certainly will be nowhere near as thoroughly tested. A simple row-sort using the slow old insertion sort could be done as follows:

#include <stdio.h>
#include <string.h>

int main (void) {

    int a[][2] = {{ 4, 5 },
                  { 2, 6 },
                  { 7, 2 },
                  { 8, 4 }},
        n = sizeof a / sizeof *a,
        col = sizeof *a / sizeof **a;

    for (int i = 0; i < n; i++) /* insertion sort of a by row */
        for (int j = i; j > 0 && *a[j] < *a[j-1]; j--) {
            int tmp[col];   /* temporary VLA */
            memcpy (tmp, a[j], sizeof *a);
            memcpy (a[j], a[j-1], sizeof *a);
            memcpy (a[j-1], tmp, sizeof *a);
        }

    for (int (*p)[2] = a; p < a + n; p++)    /* output results */
        printf ("%d, %d\n", (*p)[0], (*p)[1]);

    return 0;
}

Example Use/Output

$ ./bin/inssort2d
2, 6
4, 5
7, 2
8, 4

With qsort most new C programmers are stumped by having to write a compare function to pass to qsort to let it do its job. It is really not that difficult at all. You know qsort will pass pointers to two of whatever you are sorting as arguments to your compare function.

In this case you will be sorting rows of integers (1D arrays of integers) based on the first element of each row. So qsort will compare two int * (pointers to int). You only care about the first element in each array (which you can obtain simply by dereferencing the pointer). A compare here can be a simple:

int cmp (const void *a, const void *b)
{
    /* (a > b) - (a < b) */
    return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b);
}

(note: by using the result of the two inequalities you protect against over/underflow that could occur if you simply returned the result of a subtraction alone).

The complete qsort implementation would be:

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

int cmp (const void *a, const void *b)
{
    /* (a > b) - (a < b) */
    return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b);
}

int main (void) {

    int a[][2] = {{ 4, 5 },
                  { 2, 6 },
                  { 7, 2 },
                  { 8, 4 }},
        n = sizeof a / sizeof *a;

    qsort (a, n, sizeof *a, cmp);   /* qsort array of pointers */

    for (int (*p)[2] = a; p < a + n; p++)    /* output results */
        printf ("%d, %d\n", (*p)[0], (*p)[1]);

    return 0;
}

(output is the same)

Look over both methods and know that qsort is the preferred method, but for learning, there is nothing wrong with doing it by hand to gain experience. Let me know if you have further questions.