Как написать функцию сравнения для qsort для 2D-массива?

Question

У меня есть массив размером n * 2. Я хочу отсортировать их, используя qsort, основываясь на их значении во втором столбце.

#include<stdio.h>
int cmp(const int **a, const int **b) {
    //return 0;
    //return *a[1] - *b[1]
    // return *a - *b;
}
int main()
{
    int t; // test cases
    scanf("%d", &t);
    for(int i=0; i<t; i++)  {
        int n;
        scanf("%d", &n); // size of array
        int **arr = (int **)malloc(n * sizeof(int *)); 

        for(int j =0; j< n; j++) {
            arr[j] = (int *) malloc(2*sizeof(int));
        }
        for(int j =0; j< 2; j++) {
            for(int k =0; k< n; k++) {
              scanf("%d", &arr[k][j]);
            }
        }
        for(int k =0; k< n; k++) {
            for(int j =0; j<= 1; j++) {
             printf("%d\t", arr[k][j]);
            }
            printf("\n");
        }
       // qsort(arr, n, sizeof(arr[0]), cmp);
    }
    return 0;
}

Так что для ввода,

1 2 
3 6 
0 8 
5 4 
8 9 
5 7

Выход есть,

1 2
5 4
3 6
5 7
0 8
8 9

Я пытался, но не смог отсортировать их по 2-му столбцу. Я запутался с передачей элемента массива в компаратор. Кроме того, что передать в качестве размера элемента? Но я думаю, что первые 2 из приведенных ниже верны.

qsort(arr, n, sizeof(arr[0]), cmp);
//qsort(arr, n, sizeof((int *)), cmp);
//qsort(arr, n, 2 * sizeof((int)), cmp);

Я пробовал различные комбинации для компаратора.

Пожалуйста, укажите путь или, возможно, объяснение.

Answer 1

Прежде всего, у вас нет 2D-массива. У вас есть одномерный массив указателей, каждый из которых указывает на одномерный массив int.

Итак, вы можете отсортировать массив указателей в 1D. Для этого вы можете написать функцию сравнения, которая смотрит на значение указанного элемента.

Это может выглядеть примерно так:

int cmp(const void * a, const void * b)
{
    int* const * x = a;
    int* const * y = b;
    if ((*x)[1] < (*y)[1]) return -1;
    if ((*x)[1] > (*y)[1]) return 1;
    return 0;
}

Как сказано выше: сортируется массив указателей. Вы можете визуализировать это как:

Answer 2

Прототип для функции сравнения указан в прототипе для функции qsort:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Ваша функция сравнения должна быть совместимой, чтобы вы могли определить ее следующим образом:

int cmp(const void *a, const void *b) {
    /* a and b are pointers to the array of pointers. */
    int *aa = *(int * const *)a;
    int *bb = *(int * const *)b;
    return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}

или без приведения:

int cmp(const void *a, const void *b) {
    /* a and b are pointers to the array of pointers. */
    int * const *aa = a;
    int * const *bb = b;
    int ia = (*aa)[1];
    int ib = (*bb)[1];
    return (ia > ib) - (ia < ib);
}

Обратите внимание, что вы не можете использовать упрощенное сравнение aa[1] - bb[1], поскольку оно может переполняться при больших значениях и в лучшем случае давать неправильный вывод.

Кроме того, введенный вами цикл неверен: вы должны вкладывать циклы в обратном порядке:

    for (int k = 0; k < n; k++) {
        for (int j = 0; j < 2; j++) {
           scanf("%d", &arr[k][j]);
        }
    }

Вот модифицированная версия:

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

int cmp(const void *a, const void *b) {
    /* a and b are pointers to the array of pointers. */
    int * const *aa = a;
    int * const *bb = b;
    int ia = (*aa)[1];
    int ib = (*bb)[1];
    return (ia > ib) - (ia < ib);
}

int main() {
    int t; // test cases
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n); // size of array
        int **arr = malloc(sizeof(*arr) * n);

        for (int j = 0; j < n; j++) {
            arr[j] = malloc(sizeof(*arr[j]) * 2);
        }
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < 2; j++) {
                scanf("%d", &arr[k][j]);
            }
        }
        qsort(arr, n, sizeof(arr[0]), cmp);
        for (int k = 0; k < n; k++) {
            for(int j = 0; j < 2; j++) {
                printf("%d\t", arr[k][j]);
            }
            printf("\n");
        }
        for (int j = 0; j < n; j++) {
            free(arr[j]);
        }
        free(arr);
    }
    return 0;
}

Вы также можете упростить код, используя фактический 2D-массив:

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

int cmp(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return (aa[1] > bb[1]) - (aa[1] < bb[1]);
}

int main() {
    int t; // test cases
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n); // size of array
        int (*arr)[2] = malloc(sizeof(*arr) * n);

        for (int k = 0; k < n; k++) {
            scanf("%d%d", &arr[k][0], &arr[k][1]);
        }
        qsort(arr, n, sizeof(arr[0]), cmp);
        for (int k = 0; k < n; k++) {
            printf("%d\t%d\n", arr[k][0], arr[k][1]);
        }
        free(arr);
    }
    return 0;
}