2

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;
}
Improve this question
4
  • 1
    It is unclear what you are trying to sort. Do you want to sort each "row" of the array or the array by rows? Commented Apr 5, 2021 at 18:26
  • I'd like to sort each "row" of the array in reversed order. I'll edit my post, thanks for the hint! Commented Apr 5, 2021 at 18:27
  • 1
    You have no array at all. You have a pointer-to-pointer-to unsigned short. Commented Apr 5, 2021 at 18:27
  • 1
    Read this article for tips on debugging your code. Commented Apr 5, 2021 at 18:47

1 Answer 1

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Yes! Thank you. That's exactly what I wanted!
If you always answer the question "What are the elements I'm sorting?", and you know the compare function will take a pointer to that type -- you will never have any problems using qsort. Here, your elements were pointer to unsigned short (e.g. unsigned short*). The compare parameters are therefore unsigned short **, except if you look, the compare function takes a constant pointer, so the type is really unsigned short * const* (but unsigned short** will work, you will just be warned about discarding the const qualifier will full warnings enabled :)
Thank you for this explanation :)! I've got one (little) question: If you can't call this 2D "thing" "array", how do I have to call it instead? "A list of pointers which points to a list of integers" or is there a short name for that? Also I'm only "allowed" so say "array", if the type has this form int[], right?
An array is a specific type in C. All elements (bytes) are guaranteed to be contiguous in memory. In the case of type **nums; you have a single-pointer (to what?), a block of pointers, so you have a Pointer to Pointer to type. You allocate all pointers at once, and they will be contiguous in memory. That is why you can do num[i], but you allocate the blocks of memory holding unsigned short separately. So there isn't any correlation between the address of one block of 10 unsigned short and another. So there is no array, just a block of pointers and 10 blocks of unsigned short.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.