Использование qsort () для сортировки массива целых и подкачки строк - PullRequest
Новая
       9

Использование qsort () для сортировки массива целых и подкачки строк

0 голосов
/ 24 января 2019

Я хочу отсортировать int *arr в порядке убывания и в то же время поменять местами соответствующие элементы массива char **words, если второй элемент int *arr больше первого. Как я могу сделать это, используя qsort() и cmpfunc()? Сортировать ints было легко, но как мне поменять местами строки в другом массиве, поскольку у меня нет индекса, по которому в настоящее время сортируются два элемента массива int? 

qsort(arr,N,sizeof(int),cmpfunc);

`` 

int cmpfunc(const void * a, const void * b) {
    int val1 = *(int *)a;
    int val2 = *(int *)b;

    if(val2 > val1) {
        /* swap string positions */
        return 1;
    } else if(val2 < val1) {
        return -1;
    } else {
        return 0;
    }
}

Ответы [ 3 ]

0 голосов
/ 24 января 2019

Вы можете использовать qsort_r() (если доступно, это расширение GNU. В средах Microsoft оно называется qsort_s(), но в остальном имеет ту же семантику), чтобы передать другой аргумент в функцию сравнения, например, базовый массив указатели int *arr и char **words в структуре: 

struct cmpargs {
    int *arr;
    char **words;
} args;

...

args.arr = arr;
args.words = words;

qsort_r(arr,N,sizeof(int),cmpfunc, &args);

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

int cmpfunc(const void * a, const void * b, void *_args) {
    struct cmpargs args = _args;

    int *a1 = a;
    int *a2 = b;

    int idx1 = a - args->arr;
    int idx2 = b - args->arr;

Теперь вы можете поменять местами элементы в соответствующем массиве args->word в вашей функции сравнения, если она вернет 1.

0 голосов
/ 24 января 2019

Я хочу отсортировать int *arr в порядке убывания и в то же время поменять местами соответствующие элементы массива char **words, если второй элемент целого *arr больше первого.Как я могу сделать это, используя qsort() и cmpfunc()?

Не существует чистого способа сделать эту работу, как представлено, потому что это требует контекстной информации, которую qsort() не передает вфункция сравнения: базовые адреса массивов arr и words.Фактически, последний даже не передается самому qsort().

В реализации, которая поддерживает потоки C11, жизнеспособной альтернативой является хранение этих указателей в хранилище, специфичном для потока , и пусть функция сравнения получит их оттуда.Затем вы можете вычислить индексы сравниваемых элементов как разность указателей между ними и базовым указателем, и вы можете выполнить обычный обмен words, используя его базовый указатель и полученные вами индексы.

Но это, вероятно, не то, что вы действительно хотите! Я предполагаю, что вы пытаетесь получить ту же перестановку элементов words, что и элементов arr.То, что вы описываете, ни в коем случае не обязательно приведет к этому, потому что вы вообще не можете быть уверены, что qsort() будет выполнять своп каждый раз, когда результат сравнения будет определенным образом.

Если действительно два массива должны бытьотдельно, правильный способ сделать это состоит в том, чтобы подготовить и отсортировать некоторый вспомогательный массив.В этой области есть несколько альтернатив, которые позволят вам либо изменить порядок одного или обоих основных массивов, либо получить к ним доступ, как если бы вы это сделали.Например, вы можете подготовить int (*perm)[2], где каждый элемент (int[2]) содержит соответствующий элемент arr и начальный индекс этого элемента.Затем вы сортируете этот массив массивов так, как вам нравится, и довольно быстро получаете перестановку.Затем вы можете либо переупорядочить arr и words для соответствия, либо косвенный доступ к ним посредством перестановки (words[perm[k][1]]).

Но вы также можете подумать о написании собственной целевой сортировкифункция вместо использования qsort().Такая функция может принимать в качестве аргументов базовые указатели на оба массива - даже правильно набранные - и затем напрямую выполнять требуемую совместную сортировку.

0 голосов
/ 24 января 2019

Есть несколько способов сделать это.Во-первых, прямой ответ на ваш вопрос:

  1. Создайте новый массив size_t, содержащий значения 0 .. N.
  2. Выполните qsort для этого массивагде вместо 
int val1 = *(int *)a;
int val2 = *(int *)b;

вы делаете 

int val1 = arr[*(int *)a];
int val2 = arr[*(int *)b];

, а затем сравниваете как обычно.

Теперь у вас есть массив индексов из arr (перестановка) в порядке, в котором порядок arr будет упорядочен.Теперь мы можем применить эту перестановку к arr и words.Один из вариантов - просто циклически перемещаться по массиву индексов всякий раз, когда вы хотите получить доступ к двум массивам в отсортированном порядке.Другой способ - скопировать оба массива, а затем скопировать элементы обратно в соответствии с перестановкой.

Второе: вы также можете сделать то же самое с массивом struct { int * ; char ** } (каждый из которых указывает на одного членаarr и соответствующего члена words), отсортируйте этот массив по его члену int, оставив исходные массивы на месте, и используйте его оттуда.

В-третьих: вы можете выйтиимея параллельные массивы для начала.Если данные так тесно связаны, то почему они находятся в двух несвязанных переменных?Если вы сначала объедините два вида данных в структуре, то вы можете отсортировать массив структур и делать с этими структурами все, что захотите, не беспокоясь о том, что корреляция нарушится.

...