Linux программирование в примерах - Арнольд Роббинс

6.2.1. Сортировка: qsort()

Сортировка выполняется с помощью qsort():

#include <stdlib.h> /* ISO С */

void qsort(void *base, size_t nmemb, size_t size,

 int (*compare)(const void*, const void*));

Название qsort() происходит от алгоритма машинного поиска Хоара Quicksort (C.A.R. Hoare's Quicksort algorithm), который использовался в первоначальной реализации Unix. (Ничто в стандарте POSIX не требует использования этого алгоритма для qsort(). Реализация GLIBC использует высоко оптимизированную комбинацию Quicksort и Insertion Sort.)

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

void *base

Адрес начала массива.

size_t nmemb

Общее число элементов в массиве.

size_t size

Размер каждого элемента массива. Лучший способ получения этого значения — оператор С sizeof.

int (*compare)(const void*, const void*)

Возможно устрашающее объявление указателя функции. Оно говорит, что «compare указывает на функцию, которая принимает два параметра 'const void*' и возвращает int».

Большая часть работы заключается в написании соответствующей функции сравнения. Возвращаемое значение должно имитировать соответствующее значение strcmp(): меньше нуля, если первое значение «меньше» второго, ноль, если они равны, и больше нуля, если первое значение «больше» второго. Именно функция сравнения определяет значения «больше» и «меньше» для всего, что вы сравниваете. Например, для сравнения двух значений double мы могли бы использовать эту функцию:

int dcomp(const void *d1p, const void *d2p) {

 const double *d1, *d2;

 d1 = (const double*)d1p; /* Привести указатели к нужному типу */

 d2 = (const double*)d2p;

 if (*d1 < *d2) /* Сравнить и вернуть нужное значение */

  return -1;

 else if (*d1 > *d2)

  return 1;

 else if (*d1 == *d2)

  return 0;

 else

  return -1; /* NaN сортируется до действительных чисел */

}

Это показывает общий стереотип для функций сравнения: привести тип аргументов от void* к указателям на сравниваемый тип, а затем вернуть результат сравнения.

Для чисел с плавающей точкой простое вычитание, подобное 'return *d1 - *d2', не работает, особенно если одно значение очень маленькое или одно или оба значения являются специальными значениями «не число» или «бесконечность». Поэтому нам приходится осуществлять сравнение вручную, принимая во внимание нечисловое значение (которое даже не равно самому себе!)

6.2.1.1. Пример: сортировка сотрудников

Для более сложных структур требуются более сложные функции. Например, рассмотрите следующую (довольно тривиальную) struct employee:

struct employee {

char lastname[30];

char firstname[30];

long emp_id;

time_t start_date;

};

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

int emp_name_id_compare(const void *e1p, const void *e2p) {

 const struct employee *e1, *e2;

 int last, first;

 e1 = (const struct employee*)e1p; /* Преобразовать указатели */

 e2 = (const struct employee*)e2p;

 if ((last = strcmp(e1->lastname, e2->lastname)) != 0)

  /* Сравнить фамилии */

  return last; /* Фамилии различаются */

 /* фамилии совпадают, сравнить имена */

 if ((first = strcmp(e1->firstname, e2->firstname)) != 0)

  /* Сравнить имена */

  return first; /* Имена различаются */

 /* имена совпадают, сравнить номера ID */

 if (e1->emp_id < e2->emp_id) /* Сравнить ID сотрудника */

  return -1;

 else if (e1->emp_id == e2->emp_id)

  return 0;

 else

  return 1;

}

Логика здесь проста: сначала сравниваются фамилии, затем имена, а затем номера ID, если два имени совпадают. Используя для строк strcmp(), мы автоматически получаем правильное отрицательное/нулевое/положительное значение для возвращения.

При сравнении ID сотрудников нельзя просто использовать вычитание: представьте, что long 64-разрядный, а int 32-разрядный, а два значения отличаются лишь в старших 32 битах (скажем, младшие 32 бита равны нулю). В таком случае вычитание автоматически привело бы к приведению типа к int с отбрасыванием старших 32 битов и возвращением неверного результата.

ЗАМЕЧАНИЕ. Возможно, мы остановились при сравнении имен, в этом случае все сотрудники с совпадающими фамилиями и именами оказались бы сгруппированы, но никак не отсортированы

Это важный момент qsort() не гарантирует стабильной сортировки. Стабильна сортировка, в которой, если два элемента равны на основе значения какого-либо ключа(-ей), они сохраняют свой первоначальный порядок друг относительно друга в конечном отсортированном массиве. Например, рассмотрите трех сотрудников с одинаковыми фамилиями и именами и с номерами 17, 42 и 81. Их порядок в первоначальном массиве. возможно, был 42, 81 и 17 (Что означает, что сотрудник 42 находится по индексу с меньшим значением, чем сотрудник 81, который, в свою очередь, находится по индексу с меньшим значением, чем сотрудник 17). После сортировки порядок может оказаться 81, 42 и 17. Если ото представляет проблему, процедура сравнения должна рассматривать все важные ключевые значения (Наша так и делает.)

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

int emp_seniority_compare(const void *e1p,

 const void *e2p) {

 const struct employee *e1, *e2;

 double diff;

 /* Привести указатели к нужному типу */

 e1 = (const struct employee*)e1p;

 e2 = (const struct employee*)e2p;

 /* Сравнить времена */

 diff = difftime(e1->start_date, e2->start_date);

 if (diff < 0)

  return -1;

 else if (diff > 0)

  return 1;

 else

  return 0;

}

Для максимальной переносимости мы использовали difftime(), которая возвращает разницу в секундах между двумя значениями time_t. Для данного конкретного случая приведение, такое, как

return (int)difftime(e1->start_date, e2->start_date);

должно сработать, поскольку значения time_t находятся в приемлемом диапазоне. Тем не менее, мы вместо этого использовали полный трехсторонний оператор if, просто из предосторожности.

Вот пример файла данных со списком пяти президентов США:

$ cat presdata.txt

/* Фамилия, имя, номер президента, инаугурация */

Bush George 43 980013600

Clinton William 42 727552800

Bush George 41 601322400

Reagan Ronald 40 348861600

Carter James 39 222631200

В ch06-sortemp.c приведена простая программа, которая считывает этот файл в массив struct employee, а затем сортирует его, используя две только что представленные функции сравнения.

1   /* ch06-sortemp.c --- Демонстрирует qsort() с двумя функциями сравнения. */

2

3   #include <stdio.h>

4   #include <stdlib.h>

5   #include <time.h>

6

7   struct employee {

8    char lastname[30];

9    char firstname[30];

10   long emp_id;

11   time_t start_date;

12  };

13

14  /* emp_name_id_compare --- сравнение по имени, затем no ID */

15

16  int emp_name_id_compare(const void *e1p, const void *e2p)

17  {

     /* ...как показано ранее, опущено для экономии места... */

39  }

40

41  /* emp_seniority_compare --- сравнение по старшинству */

42

43  int emp_seniority_compare(const void *e1p, const void *e2p)

44  {

     /* ...как показано ранее, опущено для экономии места... */

58  }

59

60  /* main --- демонстрация сортировки */

61

62  int main(void)

63  {

64   #define NPRES 10

65   struct employee presidents[NPRES];

66   int i, npres;

67   char buf[BUFSIZ];

68

69   /* Очень простой код для чтения данных: */

70   for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, stdin) != NULL;

71    npres++) {

72    sscanf(buf, "%s %s %ld %ldn",

73     presidents[npres].lastname,

74     presidents[npres].firstname,

75     &presidents[npres].emp_id,

76     &presidents[npres].start_date);

77   }