cmultidimensional-arrayquicksortcomparator

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


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?


Solution

  • 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");
        }
    }