C sort 2D integer array with qsort

user_11035194 0
Viewed 112

What's your question?

I'm trying to sort a 2D integer array with the qsort function in C but I'm getting an segmentation fault. When I compile it with the following command:

gcc -g -lm -Werror -Wfatal-errors -Wall -Wextra -Wuninitialized -fsanitize=address -pedantic -Wshadow -std=c99 Test2.c

and execute it afterwards, I'm gettings this error message:

AddressSanitizer:DEADLYSIGNAL
=================================================================
==347270==ERROR: AddressSanitizer: SEGV on unknown address 0x00147fff8c06 (pc 0x556f9e44d2bb bp 0x7ffe9684a5f0 sp 0x7ffe9684a5d0 T0)
==347270==The signal is caused by a READ memory access.
    #0 0x556f9e44d2bb in compare /windows/Programming/C/Random_Stuff/Test2.c:8
    #1 0x7f17aa2718d7 in msort_with_tmp.part.0 (/usr/lib/libc.so.6+0x3e8d7)
    #2 0x7f17aa2716b4 in msort_with_tmp.part.0 (/usr/lib/libc.so.6+0x3e6b4)
    #3 0x7f17aa2716b4 in msort_with_tmp.part.0 (/usr/lib/libc.so.6+0x3e6b4)
    #4 0x7f17aa271a79 in __qsort_r (/usr/lib/libc.so.6+0x3ea79)
    #5 0x556f9e44d657 in main /windows/Programming/C/Random_Stuff/Test2.c:64
    #6 0x7f17aa25ab24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)
    #7 0x556f9e44d13d in _start (/windows/Programming/C/Random_Stuff/a.out+0x113d)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /windows/Programming/C/Random_Stuff/Test2.c:8 in compare
==347270==ABORTING

HINT: Please don't get irritated by the directory name windows, I'm on linux.

Code

Simplified example

In the following code, I'm creating a 10x10 array, which looks like this:

[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9]
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
[60, 61, 62, 63, 64, 65, 66, 67, 68, 69]
[70, 71, 72, 73, 74, 75, 76, 77, 78, 79]
[80, 81, 82, 83, 84, 85, 86, 87, 88, 89]
[90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

Now I'd like to sort these "rows" in the reversed order of the "first" array according to a specifique index of each subarray. So it should look like this in the end:

[90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
[80, 81, 82, 83, 84, 85, 86, 87, 88, 89]
[70, 71, 72, 73, 74, 75, 76, 77, 78, 79]
[60, 61, 62, 63, 64, 65, 66, 67, 68, 69]
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9]

Original case

In my original case, I have something like that:

[8,  18, 2, 20, 0]
[13, 18, 3, 15, 1]
[8,  18, 3, 30, 2]
[8,  13, 3, 15, 3]
[8,  13, 2, 10, 4]
[8,  15, 1, 7, 5]
[13, 18, 2, 10, 6]
[13, 17, 6, 24, 7]
[8,  13, 1, 5, 8]
[8,  13, 2, 10, 9]
[13, 18, 2, 10, 10]
[8,  13, 4, 20, 11]
[8,  12, 4, 16, 12]
[8,  13, 1, 5, 13]
[13, 15, 8, 16, 14]
[9,  14, 6, 30, 15]
[8,  14, 1, 6, 16]

Now I'd like to sort these "subarrays" according to the forth value of each subarray, so it should look like this:

[8,  13, 1, 5, 8]
[8,  13, 1, 5, 13]
[8,  14, 1, 6, 16]
[8,  15, 1, 7, 5]
[8,  13, 2, 10, 4]
[13, 18, 2, 10, 6]
[8,  13, 2, 10, 9]
[13, 18, 2, 10, 10]
[13, 18, 3, 15, 1]
[8,  13, 3, 15, 3]
[8,  12, 4, 16, 12]
[13, 15, 8, 16, 14]
[8,  18, 2, 20, 0]
[8,  13, 4, 20, 11]
[13, 17, 6, 24, 7]
[8,  18, 3, 30, 2]
[9,  14, 6, 30, 15]

What have you tried?

I saw this post: Sorting a 2D array with qsort but I can't find a mistake in my code if I compare it to the code of the post.

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

int compare(const void * a, const void * b)
{
    // "const void * a" points to "&nums[x]", right?
    unsigned short val1 = (*(unsigned short **) a) [3];
    unsigned short val2 = (*(unsigned short **) b) [3];

    if (val1 < val2)
        return 1;

    else if (val1 == val2)
        return 0;

    return -1;
}

int main()
{
    unsigned short **    nums;
    unsigned short       num;
    unsigned short       index;
    unsigned short       index2;
    const unsigned short length     = 10;
    const unsigned short sub_length = 10;

    /* -----------------
     * Preparations
     * ----------------- */
    nums = malloc(sizeof(unsigned short *) * length);
    num  = 0;

    if (nums == NULL)
        return EXIT_FAILURE;

    /* ------------
     * Filling
     * ------------ */
    for (index = 0; index < length; index++)
    {
        nums [index] = malloc(sizeof(unsigned short) * sub_length);

        if (nums [index] == NULL)
            return EXIT_FAILURE;

        // Fill each subarray with random nums
        for (index2 = 0; index2 < sub_length; index2++)
            nums [index][index2] = num++;
    }

    // "Before" output
    printf("Before:\n");
    for (index = 0; index < length; index++)
    {
        printf("[");
        for (index2 = 0; index2 < sub_length - 1; index2++)
            printf("%2hu, ", nums [index][index2]);
        printf("%2hu]\n", nums [index][sub_length - 1]);
    }

    // ================
    // What am I doing wrong?
    qsort(nums, length, sizeof(unsigned short) * sub_length, compare);
    // ================

    // "After" output
    printf("After:\n");
    for (index = 0; index < length; index++)
    {
        printf("[");
        for (index2 = 0; index2 < sub_length - 1; index2++)
            printf("%2hu, ", nums [index][index2]);
        printf("%2hu]\n", nums [index][sub_length - 1]);
    }

    /* ------------
     * Cleanup
     * ------------ */
    for (index = 0; index < length; index++)
        free(nums [index]);
    free(nums);

    return EXIT_SUCCESS;
}
qsort multidimensional-array c arrays
1 Answers

In order to sort the rows, you have to understand your adjacent elements for qsort will be pointers to unsigned short. Since qsort compare takes a pointer to adjacent elements that will be a pointer to pointer to unsigned short. So you have two-levels of indirection to deal with in your compare, e.g.

/* compare for adjacent ROW pointers - descending order */
int compare_desc (const void *a, const void *b)
{
    unsigned short *pa = *(unsigned short * const *)a,
                   *pb = *(unsigned short * const *)b;
    
    return (*pa < *pb) - (*pa > *pb);
}

Now a short example would be:

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

#define ROWS 10
#define COLS ROWS

/* compare for adjacent ROW pointers - descending order */
int compare_desc (const void *a, const void *b)
{
    unsigned short *pa = *(unsigned short * const *)a,
                   *pb = *(unsigned short * const *)b;
    
    return (*pa < *pb) - (*pa > *pb);
}

int main (void) {
    
    unsigned short **nums = NULL;
    
    nums = malloc (ROWS * sizeof *nums);
    if (!nums) {
        perror ("malloc-nums");
        exit (EXIT_FAILURE);
    }
    
    for (int i = 0; i < ROWS; i++) {
        nums[i] = malloc (COLS * sizeof *nums[i]);
        if (!nums[i]) {
            perror ("malloc-nums[i]");
            exit (EXIT_FAILURE);
        }
        for (int j = 0; j < COLS; j++) {
            nums[i][j] = i * COLS + j;
            printf (j ? " %3hu" : "%3hu", nums[i][j]);
        }
        putchar ('\n');
    }
    
    qsort (nums, ROWS, sizeof *nums, compare_desc);
    
    puts ("\nrows sorted descending, columns sorted ascending\n");
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++)
            printf (j ? " %3hu" : "%3hu", nums[i][j]);
        putchar ('\n');
        free (nums[i]);
    }
    free (nums);
}

Example Use/Output

$ ./bin/qsort_ptr2ptr
  0   1   2   3   4   5   6   7   8   9
 10  11  12  13  14  15  16  17  18  19
 20  21  22  23  24  25  26  27  28  29
 30  31  32  33  34  35  36  37  38  39
 40  41  42  43  44  45  46  47  48  49
 50  51  52  53  54  55  56  57  58  59
 60  61  62  63  64  65  66  67  68  69
 70  71  72  73  74  75  76  77  78  79
 80  81  82  83  84  85  86  87  88  89
 90  91  92  93  94  95  96  97  98  99

rows sorted descending, columns sorted ascending

 90  91  92  93  94  95  96  97  98  99
 80  81  82  83  84  85  86  87  88  89
 70  71  72  73  74  75  76  77  78  79
 60  61  62  63  64  65  66  67  68  69
 50  51  52  53  54  55  56  57  58  59
 40  41  42  43  44  45  46  47  48  49
 30  31  32  33  34  35  36  37  38  39
 20  21  22  23  24  25  26  27  28  29
 10  11  12  13  14  15  16  17  18  19
  0   1   2   3   4   5   6   7   8   9

Let me know if that is what you were after and if you have further questions.

user_34221020
Related