qsort не работает должным образом с длинным длинным

Я сортирую двумерный массив a[n][2], относительно a[i][0],a[i+1][0] разрывая связи с неубывающим a[i][1],a [я+1][1]. qsort отлично работает с целочисленным массивом, но не с длинным массивом.

Код целочисленного массива

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int cmpfunc(const void* a, const void* b)
{
    int x = ((int*)a)[0] - ((int*)b)[0];
    if (x != 0) {
        return x;
    }
    return ((int*)a)[1] - ((int*)b)[1];
}

int main(int argc, char const* argv[])
{
    int n, i, j;
    scanf("%d", &n);
    int a[n][2];
    for (i = 0; i < n; i = i + 1) {
        scanf("%d %d", &a[i][0], &a[i][1]);
    }
    qsort(a, n, sizeof(a[0]), cmpfunc);
    for (i = 0; i < n; i = i + 1) {
        printf("%d %d\n", a[i][0], a[i][1]);
    }
    return 0;
}

длинный длинный код массива

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int cmpfunc(const void* a, const void* b)
{
    int x = ((int*)a)[0] - ((int*)b)[0];
    if (x != 0) {
        return x;
    }
    return ((int*)a)[1] - ((int*)b)[1];
}

int main(int argc, char const* argv[])
{
    int n, i, j;
    scanf("%d", &n);
    long long a[n][2];
    for (i = 0; i < n; i = i + 1) {
        scanf("%I64d %I64d", &a[i][0], &a[i][1]);
    }
    qsort(a, n, sizeof(a[0]), cmpfunc);
    for (i = 0; i < n; i = i + 1) {
        printf("%I64d %I64d\n", a[i][0], a[i][1]);
    }
    return 0;
}

Вход:

5
4 3
4 2
4 1
4 1
4 1

Вывод для первого кода:

4 1
4 1
4 1
4 2
4 3

Вывод для второго кода:

4 2
4 1
4 1
4 1
4 3

c qsort long-long
person Vishal    schedule 06.07.2017    source источник
comment
В случае, когда вы используете long long, вы ничего не забыли? Особенно в функции сравнения? Каков фактический тип a и b?   -  person Some programmer dude    schedule 06.07.2017
comment
Я предлагаю вам научиться отлаживать свой код. Начните с добавления операторов printf() для просмотра значений переменных.   -  person Code-Apprentice    schedule 06.07.2017
comment
@Someprogrammerdude Какое это имеет значение? ввод все еще находится в диапазоне int, он также должен работать с int * cast, верно?   -  person Vishal    schedule 06.07.2017
comment
Ваш код не имеет смысла. Вы не понимаете, как работает qsort().   -  person Stargateur    schedule 06.07.2017
comment
Также есть проблема, что qsort передает указатели на элементы в функцию сравнения, т.е. она передает &a[0] (используя массив a в функции main), которые имеют тип long long (*)[2].   -  person Some programmer dude    schedule 06.07.2017

Ответы (3)


arrow_upward
1
arrow_downward

На самом деле у вас есть две проблемы: первая связана с недопустимым приведением типов. Второй — тоже о недопустимом приведении, но по другой причине.

Как указано в одном из моих комментариев, функция qsort передает указатели на элементы в функцию сравнения. Если у вас есть массив arr, то qsort будет использовать что-то вроде &arr[0] для аргументов. Это означает, что если данные массива сами по себе являются массивами, то аргументы будут указателями на массивы. В вашем конкретном случае типы аргументов действительно long long (*)[2], а не только long long *.

Таким образом, функция сравнения должна выглядеть примерно так:

int cmpfunc(const void* a_, const void* b_)
{
    long long (*a)[2] = (long long (*)[2]) a_;
    long long (*b)[2] = (long long (*)[2]) b_;

    long long result;

    if ((*a)[0] - (*b)[0] != 0)
        result = (*a)[0] - (*b)[0];
    else
        result = (*a)[1] - (*b)[1];

    if (result < 0)
        return -1;
    else if (result > 0)
        return 1;
    else
        return 0;
}
person Some programmer dude    schedule 06.07.2017
comment
Можно ли сохранить спецификатор const? да, не нужно приводить, просто работает long long const (*a)[2] = a_;. - person Stargateur; 06.07.2017
comment
Результат разницы между двумя long long int не может быть в диапазоне int, поэтому эту реализацию qsort использовать нельзя. Это неправильно? Также ваш код не работает должным образом для этого вопроса, вы должны попробовать, потому что настоящая проблема заключается в scanf заполнителях. - person simo-r; 06.07.2017
comment
@BetaRunner Вы правы, что в общем случае разница может быть больше. Обновлен ответ, чтобы сохранить результат вычитания в переменной и использовать его для возврата int. - person Some programmer dude; 06.07.2017
comment
Является ли return (*a)[0] - (*b)[0]; действительным в int cmpfunc(...), когда a и b относятся к типу long long (*)[2]? Разница в long long, и я боюсь, что приведение к возвращаемому типу int может урезать или обернуть результат вокруг нуля. ИМХО, в этом случае лучше использовать вложенный if, чтобы вернуть int значение 1 или -1 в зависимости от того, разница больше или меньше (long long)0, а по умолчанию return 0; после того, как все if-less и if-больше терпят неудачу. EDIT К сожалению, слишком долго пишется перед сохранением. - person CiaPan; 06.07.2017
comment
@Someprogrammerdude В коде вопроса он предполагает, что long long int - это 64-bit, что не всегда верно, и он также использует заполнители int вместо long long int. Я думаю, что вы также должны показать, как исправить это (?) - person simo-r; 06.07.2017
comment
@BetaRunner long long минимум 64 бита. И я еще не видел системы с большим (например, 128-битным) типом long long. VC++ (который имеет формат "%I64d" в качестве специального расширения) наверняка не имеет не-64-битного long long. И эта проблема в любом случае для другого вопроса. Однако вы можете указать это для ОП в качестве комментария к вопросу. - person Some programmer dude; 06.07.2017
comment
@BetaRunner он предполагает, что long long int является 64-битным. Я думаю, вы слишком много внимания уделяете ОП. Кажется, он не понимает отношения между указателями и размером данных, на которые он указывает. - person Code-Apprentice; 06.07.2017

arrow_upward
1
arrow_downward

Вы по-прежнему приводите к int * в своей функции сравнения, даже если вы изменили тип данных на long long.

person Art    schedule 06.07.2017
comment
Какое это имеет значение? ввод все еще находится в диапазоне int. - person Vishal; 06.07.2017
comment
@Vishal А что, если sizeof(long long) != sizeof(int)? Что весьма вероятно (long long - это как минимум 64 бита, int обычно 32 бита даже в 64-битных системах). - person Some programmer dude; 06.07.2017
comment
@Vishal Обратите внимание, что если бы вы приводили значение long long к int и значение находилось в диапазоне int, у вас не было бы проблем. Однако вы вводите long long * в int *, что сильно отличается. Диапазон значений не имеет значения при работе с указателями. - person Code-Apprentice; 06.07.2017
comment
@Code-Apprentice Я понимаю, он работает с long long * cast вместо int*, можете ли вы объяснить, что произойдет в случае long long * to int* cast? - person Vishal; 06.07.2017
comment
@Vishal Как уже упоминалось, long long и int имеют разные размеры. - person Code-Apprentice; 06.07.2017

arrow_upward
0
arrow_downward

Если вы включите предупреждение во время компиляции (-Wall -pedantic для gcc), вы должны заметить, что вам нужен другой заполнитель для long long int, и вы не можете предположить, что это 64-bit. Вы также неверно используете аргументы функции сравнения. Обратите внимание, что разница между двумя long long int может быть за пределами диапазона int, поэтому вы не можете использовать эту (тот, что я написал) реализацию qsort() сравнения. Вот код:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmpfunc(const void *a,const void *b){
    long long int x=((long long int *)a)[0]-((long long int *)b)[0];
    if(x!=0){
        return x;
    }
    return ((long long int *)a)[1]-((long long int *)b)[1];
    }


int main(int argc, char const *argv[]){
    int n,i;
    scanf("%d",&n);
    long long a[n][2];
    for(i=0;i<n;i=i+1){
        scanf("%lld %lld",&a[i][0],&a[i][1]);
    }
    qsort(a,n,sizeof(a[0]),cmpfunc);
    for(i=0;i<n;i=i+1){
        printf("%lld %lld\n",a[i][0],a[i][1]);
    }
    return 0;
}
person simo-r    schedule 06.07.2017