How do I use quicksort in C with a multi-dimensional array? I am getting an incorrect result - Stack Overflow

admin管理员组

文章数量:1399499

I am trying to sort the tuples in the 2D array based on a single column value similar to Javascript's sort function.

arr.sort((a,b) => a[0] - b[0])

C Code :

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

    int comp(const void *a, const void *b){
        return (((int*)a)[0] - ((int *)b)[0]);
    }
    int main(){
        int arr[][4] = {
           {3,2,5,3}, {1,0,5,2},{0,2,2,4},{0,4,4,5}
        };
        int ROWS = sizeof(arr)/sizeof(arr[0]);
        int COLS = sizeof(arr[0])/sizeof(arr[0][0]);
        //qsort(arr, ROWS, COLS*sizeof(int), comp); //this works and sorts arr correctly
    

    int **rect = malloc(ROWS*sizeof(int*));

    for(int i = 0; i < COLS; i++){
        *(rect+i) = malloc(COLS*sizeof(int));
    }
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            *(*(rect+i)+j) = arr[i][j];
        }
    }

    qsort(rect, ROWS, COLS*sizeof(int), comp); //this doesn't work on the rect 2d array.
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            printf("%d ", *(*(rect+i)+j));
        }
        printf("\n");
    }
}

Quicksort works with the comparator function on the 2D array arr.

When I try using it with the **rect array, the sorting doesn't work. I end up getting a segmentation fault. Can somebody point out where I am going wrong and how **rect is being treated differently from arr?

I am trying to sort the tuples in the 2D array based on a single column value similar to Javascript's sort function.

arr.sort((a,b) => a[0] - b[0])

C Code :

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

    int comp(const void *a, const void *b){
        return (((int*)a)[0] - ((int *)b)[0]);
    }
    int main(){
        int arr[][4] = {
           {3,2,5,3}, {1,0,5,2},{0,2,2,4},{0,4,4,5}
        };
        int ROWS = sizeof(arr)/sizeof(arr[0]);
        int COLS = sizeof(arr[0])/sizeof(arr[0][0]);
        //qsort(arr, ROWS, COLS*sizeof(int), comp); //this works and sorts arr correctly
    

    int **rect = malloc(ROWS*sizeof(int*));

    for(int i = 0; i < COLS; i++){
        *(rect+i) = malloc(COLS*sizeof(int));
    }
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            *(*(rect+i)+j) = arr[i][j];
        }
    }

    qsort(rect, ROWS, COLS*sizeof(int), comp); //this doesn't work on the rect 2d array.
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            printf("%d ", *(*(rect+i)+j));
        }
        printf("\n");
    }
}

Quicksort works with the comparator function on the 2D array arr.

When I try using it with the **rect array, the sorting doesn't work. I end up getting a segmentation fault. Can somebody point out where I am going wrong and how **rect is being treated differently from arr?

• c
• multidimensional-array
• quicksort
• comparator

Share Improve this question Follow asked Mar 25 at 12:39 Bittu970Bittu970 10711 silver badge66 bronze badges 7

• 4 rect is not a multidimensional array but a pointer to a pointer. Pointers are very different from arrays. (((int*)a)[0] accesses a pointer and interpretes it as a int. – Gerhardh Commented Mar 25 at 13:04
• 4 *(rect+i) = do yourself any everyone else a favor and use array notation: rect[i] = – Gerhardh Commented Mar 25 at 13:07
• 1 @Bittu970 qsort(rect, ROWS, COLS*sizeof(int), comp); fails as the size is wrong. Should be qsort(rect, ROWS, sizeof rect[0], comp);. But then that is not sorting an array of int. If you want a 2D array, allocate a 2D array and not an array of pointers to arrays. What is the real goal? A 2d array or an array of pointers to arrays? – chux Commented Mar 25 at 13:13
• @chux I am doing a leetcode question and the input provided (2D array) is of the form pointer to array of pointers. I need to sort this array. That's why I want to understand how to make qsort work with array of pointers to arrays because there are several questions there that provide input in that manner. This is the question : leetcode/problems/check-if-grid-can-be-cut-into-sections/…. and the input : bool checkValidCuts(int n, int** rectangles, int rectanglesSize, int* rectanglesColSize) – Bittu970 Commented Mar 25 at 13:21
• Again, a pointer to an array of pointers is not a 2D array. It can be used in many ways like a 2D array, but it is crucially important to understand their differences. – John Bollinger Commented Mar 25 at 13:32

 |  Show 2 more comments

2 Answers 2

Sorted by: Reset to default 2

The objects being sorted are of type int * and are being sorted in ascending order of the first int element they point to. See the definition of the function comp2, and the call to qsort in the following, modified code:

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

int comp2(const void *a, const void *b){
    int *aa = *(int * const *)a;
    int *bb = *(int * const *)b;
    // N.B. this expression is immune from integer overflow, unlike aa[0] - bb[0]
    return (aa[0] > bb[0]) - (aa[0] < bb[0]);
}

int main(){
    static const int arr[][4] = {
       {3,2,5,3}, {1,0,5,2},{0,2,2,4},{0,4,4,5}
    };
    int ROWS = sizeof(arr)/sizeof(arr[0]);
    int COLS = sizeof(arr[0])/sizeof(arr[0][0]);

    int **rect = malloc(ROWS*sizeof(int*));

    // N.B. OP's original code incorrectly used i < COLS here...
    for(int i = 0; i < ROWS; i++){
        rect[i] = malloc(COLS*sizeof(int));
    }
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            rect[i][j] = arr[i][j];
        }
    }

    qsort(rect, ROWS, sizeof(rect[0]), comp2);
    for(int i = 0; i < ROWS; i++){
        for(int j = 0; j < COLS; j++){
            printf("%d ", rect[i][j]);
        }
        printf("\n");
    }
}

Use pointers to array

int main()
{

    int arr[][4] = {
        {3,2,5,3}, 
        {1,0,5,2},
        {0,2,2,4},
        {0,4,4,5}};
    size_t ROWS = sizeof(arr)/sizeof(arr[0]);
    size_t COLS = sizeof(arr[0])/sizeof(arr[0][0]);

    /* pointer to array */ // <<----
    int (*rect)[COLS] = malloc(ROWS * sizeof(*rect));

    for(size_t i = 0; i < ROWS; i++)
    {
        for(size_t j = 0; j < COLS; j++)
        {
            rect[i][j] = arr[i][j];
        }
    }

    qsort(rect, ROWS, sizeof(*rect), comp); 
    for(size_t i = 0; i < ROWS; i++)
    {
        for(size_t j = 0; j < COLS; j++)
        {
            printf("%d ", rect[i][j]);
        }
        printf("\n");
    }
    free(rect);
}

本文标签： How do I use quicksort in C with a multidimensional array I am getting an incorrect resultStack Overflow