Шрифт:
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 {
/* ...как показано ранее, опущено для экономии места... */