Сортируем массив данных стандартными средствами Cи

newbie_

Опубликован:  2019-10-21T08:06:11.394141Z

В одном из выпусков блога была продемонстрирована работа классического алгоритма сортировки массива данных - сортировка вставками, сегодня я покажу инструмент для сортировки массивов из стандартной библиотеки C, продемонстрирую создание и заполнение массива из строк, содержащих случайные числа, и отсортирую такой массив.

Последние несколько недель я был занят чтением довольно любопытной книжки - C Primer Plus by Stephen Prata в шестой редакции. Теория всегда отнимает достаточно много сил и времени, но тем не менее, без теории не может быть практики. В одной из глав этой книги рассматривается функция стандартной библиотеки qsort, и приводится пример формирования массива случайных дробных чисел и последующей его сортировки. Мне стало интересно реализовать аналогичные действия с массивом данных, в котором каждый элемент будет представлять строку. На практике не всё пошло гладко, но в результате цель всё же была достигнута, это описание продемонстрирует все трудности, с которыми пришлось столкнуться, и методы их решения.

Итак, запускаю привычный и достаточный для решения этой задачи Geany, создаю новый файл - qssorter.c.

nZ5tqnX8hz.png

Одну большую задачу удобно разделить на несколько мелких, каждая из которых будет специализироваться на конкретных действиях, так я и поступлю в данном случае. Первая задача, которую мне нужно решить, - это построить функцию, которая компоновала бы случайным образом строку, состоящую из цифр от 0 до 9 включительно.

Пишу код... На начальном этапе мне потребуются следующие заголовочные файлы:

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

#define SIZE 4

Файл stdlib.h содержит декларации функций srand, rand, mallocfree), с их помощью я определю функцию, которая сформирует строку из следующих в случайном порядке цифр и вернёт указатель на первый символ этой строки. Прототип такой функции будет выглядеть следующим образом:

char * randomize(unsigned int n);

В качестве аргумента функции я задал целое число n, которое будет определять длину формируемой строки, то есть количество символов в этой строке. Определяю эту функцию так:

char * randomize(unsigned int n)
{
  unsigned int i;
  char * res;
  res = (char *) malloc((n + 1) * sizeof *res);
  for (i = 0; i < n; i++)
    *(res + i) = rand() % 10 + 48;
  return res;
}

Здесь я создал переменную res - указатель на char, зарезервировал необходимый для хранения строки объём оперативной памяти с помощью функции malloc, и заполнил полученный массив с помощью функции rand следующими в случайном порядке цифрами от 0 до 9, а полученный в результате выполненных действий указатель вернул.

Протестирую randomize, для этого в функции main программы пишу следующее:

int main(void)
{
  srand(time(0));
  char * s = randomize(SIZE);
  printf("%s\n", s);
  free(s);
  return 0;
}

Чтобы случайные числа действительно были случайными, мне необходим вызов функции srand, в параметре которой задан вызов функции time (прототип этой фунции содержится в заголовочном файле time.h). Создаю строку s и вывожу её на печать. Поскольку пространство под строку s зарезервировано при помощи malloc, его необходимо освободить, для этого потребовался вызов free. Компилирую полученную программу и пробую её запустить несколько раз подряд.

gcc -o exe -Wall qssorter.c
./exe

fzD4ALWN7d.png

Здесь следует обратить внимание, что для компиляции я использую опцию компилятора -Wall, которая определяет, что компилятор будет выдавать в выхлоп все возможные предупреждения. Компиляция завершилась без ошибок и предупреждений, есть шанс, что код написан верно. В результате многократного исполнения программы, в выхлопе каждый раз новая случайная строка. С первой частью задачи я справился.

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

void fillarray(char ** ar, unsigned int n, unsigned int s);
void showarray(char * const * ar, unsigned int n);
void freearray(char ** ar, unsigned int n);

Признаюсь, самой сложной сложностью в данном случае для меня стал первый аргумент этих функций, во всех трёх случаях этот аргумент определяет массив из указателей на соответствующие строки, только в функциях fillarray и freearray строки могут быть изменены, а в функции showarray эти строки являются константами, их значения нельзя изменить. Не уверен, что всё сделал правильно, по-крайней мере такой код компилируется без предупреждений и ошибок, а затем работает как задумано.

Начнём с определения fillarray. На входе я получаю массив из указателей на строки, длину формируемого массива - n, и длину каждой хранящейся в массиве строки - s. Строки я буду определять при помощи функции randomize.

void fillarray(char ** ar, unsigned int n, unsigned int s)
{
  unsigned int i;
  for (i = 0; i < n; i++)
    ar[i] = randomize(s);
}

Один простой цикл формирует необходимый по условию задачи массив данных.

Функция showarray должна вывести на экран все хранящиеся в массиве строки в заданной форме, для этого достаточно знать только длину массива.

void showarray(char * const * ar, unsigned int n)
{
  unsigned int i;
  for (i = 0; i < n; i++)
  {
    printf("%s  ", ar[i]);
    if (i % 6 == 5)
      putchar('\n');
  }
  if (i % 6 != 0)
    putchar('\n');
}

Функция freearray должна освободить зарезервированное под строки пространство оперативной памяти компьютера, её код элементарен.

void freearray(char ** ar, unsigned int n)
{
  unsigned int i;
  for (i = 0; i < n; i++)
    free(ar[i]);
}

Имея эти инструменты, я могу получить необходимый по условию задачи массив и вывести хранящиеся в нём данные на экран. Редактирую функцию main.

#define NUM 40

...

int main(void)
{
  srand(time(0));
  char * nums[NUM];
  fillarray(nums, NUM, SIZE);
  puts("Initial data:");
  showarray(nums, NUM);
  freearray(nums, NUM);
  return 0;
}

Попробуем откомпилировать этот код и исполнить полученную в результате программу.

gcc -o exe -Wall qssorter.c 
./exe

1ReUzhuoWe.png

Отлично..! С первой частью марлезонского балета я справился, теперь у меня есть массив из сорока случайных строк, и я могу данные из этого массива вывести на экран. Давайте посмотрим на функцию qsort, прототип которой хранится в заголовочном файле stdlib.h. В теории, этот массив можно отсортировать данной функцией, попробуем написать практическую реализацию этой задачи.

Прототип функции qsort выглядит следующим образом:

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

Первый аргумент функции - это указатель на первый элемент сортируемого массива.

Второй аргумент функции определяет количество элементов в сортируемом массиве.

Третий аргумент функции задаёт размер каждого элемента сортируемого массива.

Четвёртый аргумент функции определяет функцию, при помощи которой будет задан порядок сортировки, в данном случае аргумент является указателем на функцию.

Чтобы воспользоваться функцией qsort, мне необходимо правильно задать параметры в вызове этой функции. Самой сложной задачей оказалось определение функции, задающей порядок сортировки - четвёртый аргумент. Эта функция по задумке авторов в аргументах должна принимать указатели на void, а в теле функции эти указатели должны быть преобразованы в указатели на строки, а затем определён порядок сравнения этих двух строк. Реализация этой функции в итоге стоила мне пару клочков волос, выдранных из собственной головы. И вот то, что у меня получилось.

...
// в string.h определён прототип strcmp
#include <string.h>

...
// прототип функции, определяющей порядок сортировки массива
int compare(const void * p1, const void * p2);

...

int compare(const void * p1, const void * p2)
{
  return strcmp(*(char * const *) p1, *(char * const *) p2);
}

Имея такую функцию и сформированный массив данных, я могу этот массив отсортировать в порядке возрастания, то есть меньшие значения будут следовать в начале массива, большие в конце массива. Редактирую функцию main.

int main(void)
{
  srand(time(0));
  char * nums[NUM];
  fillarray(nums, NUM, SIZE);
  puts("Initial data:");
  showarray(nums, NUM);
  qsort(nums, NUM, sizeof(char **), compare);
  puts("\nSorted data:");
  showarray(nums, NUM);
  freearray(nums, NUM);
  return 0;
}

Компилирую и пробую исполнить программу.

gcc -o exe -Wall qssorter.c
./exe

9kvdCxTmgv.png

Следует заметить, что g++ тоже без труда справляется с этим кодом.

tIwtbABWdp.png

Как известно, практика подтверждает теорию, только если теория хорошо изучена. Код работает, хоть я до конца и не уверен, что всё в этом коде правильно. Если у Вас есть замечания, напишите в комментариях, что я сделал не так.

В качестве вывода... Без иронии хочу сказать, что программисты на C - мужественные люди, они обладают завидным интеллектуальным потенциалом, очень наблюдательны и имеют хорошие аналитические способности. Теперь, когда я попробовал окунуться в теорию программирования на C, мне стало понятно, почему в вакансиях российских IT компаний очень редко встречаются программисты на C - таких специалистов очень сложно подготовить и поэтому ещё сложней переманить из других компаний, и практически невозможно найти уже подготовленных свободных.

qssorter.c

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

#define SIZE 4
#define NUM 40

char * randomize(unsigned int n);
void fillarray(char ** ar, unsigned int n, unsigned int s);
void showarray(char * const * ar, unsigned int n);
void freearray(char ** ar, unsigned int n);
int compare(const void * p1, const void * p2);

int main(void)
{
  srand(time(0));
  char * nums[NUM];
  fillarray(nums, NUM, SIZE);
  puts("Initial data:");
  showarray(nums, NUM);
  qsort(nums, NUM, sizeof(char **), compare);
  puts("\nSorted data:");
  showarray(nums, NUM);
  freearray(nums, NUM);
  return 0;
}

int compare(const void * p1, const void * p2)
{
  return strcmp(*(char * const *) p1, *(char * const *) p2);
}

void fillarray(char ** ar, unsigned int n, unsigned int s)
{
  unsigned int i;
  for (i = 0; i < n; i++)
    ar[i] = randomize(s);
}

void freearray(char ** ar, unsigned int n)
{
  unsigned int i;
  for (i = 0; i < n; i++)
    free(ar[i]);
}

void showarray(char * const * ar, unsigned int n)
{
  unsigned int i;
  for (i = 0; i < n; i++)
  {
    printf("%s  ", ar[i]);
    if (i % 6 == 5)
      putchar('\n');
  }
  if (i % 6 != 0)
    putchar('\n');
}

char *randomize(unsigned int n)
{
  unsigned int i;
  char * res;
  res = (char *) malloc((n + 1) * sizeof *res);
  for (i = 0; i < n; i++)
    *(res + i) = rand() % 10 + 48;
  return res;
}
Комментарии: