Как отсортировать строки 2D-матрицы с помощью qsort?

Многие мои коллеги спрашивали меня, можно ли отсортировать каждую строку 2D-массива, используя функцию qsort() из <stdlib.h>, чтобы упорядочить матрицу, например:

 5,  8,  7,  6, 
 1,  4,  3,  2, 
11, 12, 10,  9, 

во что-то вроде:

 5,  6,  7,  8, 
 1,  2,  3,  4, 
 9, 10, 11, 12, 

person PatrickSteiner    schedule 30.10.2017    source источник
comment
Конечно, строка в 2D-массиве — это просто 1D-массив. Вы можете сортировать каждую строку так же, как и любой другой массив.   -  person Code-Apprentice    schedule 30.10.2017
comment
Возможный дубликат Qsorting 2d массивов указателей   -  person Code-Apprentice    schedule 30.10.2017
comment
@Code-Apprentice не совсем, этот вопрос о массиве указателей ... но все же я не совсем понимаю здесь.   -  person    schedule 30.10.2017
comment
@FelixPalmen В этом вопросе нет объявления точного типа двумерного массива. И в предложенном решении ничего не сказано об указателях.   -  person Code-Apprentice    schedule 30.10.2017
comment
@ Code-Apprentice, да? Здесь речь идет о 2d-массиве, и предлагаемое решение показывает код, обрабатывающий 2d-массив. Вместо этого кандидат-дубликат представляет собой массив указателей. Как я уже сказал, я не понимаю здесь, но это не (точная) копия.   -  person    schedule 30.10.2017
comment
этот вопрос касается массива указателей. В контексте я понял, что это означает этот вопрос прямо здесь, где мы комментируем, который не имеет ничего общего с указателями. Вы правы насчет этого вопроса, который я предложил как дубликат, касается указателей. Путаница прояснилась для меня теперь, спасибо ;-)   -  person Code-Apprentice    schedule 30.10.2017


Ответы (2)


Решение проблемы выглядит следующим образом:

#include <stdio.h>   // scanf() printf()
#include <stdlib.h>  // qsort()

int compare (const void *a, const void *b)
{
  int x = *(int *)a;
  int y = *(int *)b;

  if (x<y) return -1; 
  if (x>y) return 1; 
  return 0;
}

int main()
{
  // Syntax of a 2D Array: array[rows][cols]
  int rows = 3, cols = 4;
  int array[3][4] = { {5,8,7,6,}, {1,4,3,2}, {11,12,10,9} };

  // Print the matrix unsorted:
  printf("\nUnsorted rows:\n");
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      printf("%2d, ", array[i][j]);
    }
    printf("\n");
  }

  // Sort the matrix using qsort:
  for(int j = 0; j < rows; j++)
    qsort(array[j], cols, sizeof(int), compare);

  // Print the matrix sorted:
  printf("\nSorted rows:\n");
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      printf("%2d, ", array[i][j]);
    }
    printf("\n");
  }

  return 0;
}

Вывод:

Unsorted rows:
 5,  8,  7,  6, 
 1,  4,  3,  2, 
11, 12, 10,  9, 

Sorted rows:
 5,  6,  7,  8, 
 1,  2,  3,  4, 
 9, 10, 11, 12, 

Спасибо flukey за полезный ответ в: Qsorting 2d массивы указателей

person PatrickSteiner    schedule 30.10.2017
comment
И что этот вопрос / ответ дает по сравнению с оригиналом, на который вы ссылаетесь? - person ; 30.10.2017
comment
compare нуждается { } - person BLUEPIXY; 30.10.2017
comment
return ( *(int*)a - *(int*)b ); ‹- остерегайтесь переполнения. - person ; 30.10.2017
comment
@FelixPalmen знаете ли вы лучшее решение проблемы переполнения? - person PatrickSteiner; 30.10.2017
comment
@PatrickSteiner, чтобы он оставался читаемым, выполните int x = *(int *)a; int y = *(int *)b;, затем return (x>y) - (x<y); или более подробный и немного более читаемый с тем же результатом if (x<y) return -1; if (x>y) return 1; return 0; - person ; 30.10.2017
comment
Вы не должны отбрасывать const в функции сравнения. Преобразование из const void* в int* не является четко определенным. Вы должны были получить предупреждения компилятора. Вместо этого приведите к const int*. - person Lundin; 30.10.2017
comment
@Lundin: ты уверен? Если бы результат приведения был назначен указателю на неконстанту, тогда у вас был бы случай, но в нынешнем виде, я считаю, все в порядке. (Я думаю, что недавно видел часть стандарта об этом, но я не смог найти ее снова. Я заменю этот комментарий другим, если получу x-ref.) - person Jonathan Leffler; 30.10.2017
comment
Альтернативой удобочитаемой и расширяемой схеме сравнения, описанной Феликсом, является return (x > y) - (x < y);, которая требует осторожности, чтобы правильно подобрать термины, и (по крайней мере, пока оптимизатор не начнет работать) требует двух сравнений и вычитания. Будьте осторожны при использовании этого, но он позволяет избежать переполнения. - person Jonathan Leffler; 30.10.2017
comment
@JonathanLeffler Само преобразование является неопределенным поведением, поскольку оно не распространяется на стандарт C. 6.3.2.3/2 упоминает только то, что четко определено: For any qualifier q, a pointer to a non-q-qualified type may be converted to a pointer to the q-qualified version of the type; the values stored in the original and converted pointers shall compare equal. Нет документированного поведения для противоположного: квалифицированный указатель на тип преобразуется в указатель на тип. Пустые указатели не должны быть исключением из правила. - person Lundin; 30.10.2017
comment
@Lundin: я нашел то, что вы цитируете в моем поиске, когда печатал мой предыдущий комментарий о приведениях. В §6.5.4 Операторы приведения есть сноска 104: Приведение не дает lvalue. Таким образом, приведение к квалифицированному типу имеет тот же эффект, что и приведение к неквалифицированной версии типа. Теперь сноски не являются нормативными, поэтому приведенная вами цитата из §6.3.2.2 § 2 имеет приоритет над цитатой. сноска. Это означает, что ваш комментарий верен, я думаю. - person Jonathan Leffler; 30.10.2017
comment
@JonathanLeffler И что бы это ни стоило, компиляторы и статические анализаторы склонны стонать, если у вас нет приведения, и тем самым вызывают неявное преобразование указателя - поскольку мы имеем дело с указателями void, явное приведение не должно быть необходимо. Если только он не был специально помещен туда, чтобы отбросить квалификатор. В любом случае, это плохая практика и подозрительный код. - person Lundin; 31.10.2017

Патрик,

Представьте себе двумерный массив как комбинацию множества одномерных массивов.

Выполните сортировку каждого из 1d массивов (строк), используя 2 цикла. Один цикл для итерации по (столбцам) и один по массивам 1d. Во втором внутреннем цикле вы можете выполнять сортировку.

person Rakshith Murukannappa    schedule 30.10.2017
comment
Добро пожаловать в Stack Overflow. Поскольку сортировка должна выполняться в каждой строке, почему вы предлагаете перебирать столбцы? Как вы интерпретируете int array[3][4]; — массив из 3 строк по 4 столбца в строке или что-то еще? Можете ли вы обрисовать свой код? В нынешнем виде ваш совет кажется нецелесообразным. - person Jonathan Leffler; 30.10.2017