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

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 %ld ",

73     presidents[npres].lastname,

74     presidents[npres].firstname,

75     &presidents[npres].emp_id,

76     &presidents[npres].start_date);

77   }

78

79   /* npres теперь содержит число прочитанных строк. */

80

81   /* Сначала сортировка по имени */

82   qsort(presidents, npres, sizeof(struct employee), emp_name_id_compare);

83

84   /* Вывести результат */

85   printf("Sorted by name: ");

86   for (i = 0; i < npres; i++)

87    printf(" %s %s %d %s",

88     presidents[i].lastname,

89     presidents[i].firstname,

90     presidents[i].emp_id,

91     ctime(&presidents[i].start_date));

92

93   /* Теперь сортировка по старшинству */

94   qsort(presidents, npres, sizeof(struct employee), emp_seniority_compare);

95

96   /* И снова вывести */

97   printf("Sorted by seniority: ");

98   for (i = 0; i < npres; i++)

99    printf(" %s %s %d %s",

100    presidents[i].lastname,

101    presidents!i].firstname,

102    presidents[i].emp_id,

103    ctime(&presidents[i].start_date));

104 }

Строки 70–77 считывают данные. Обратите внимание, что любое использование scanf() требует от входных данных «хорошего поведения». Если, например, какое-нибудь имя содержит более 29 символов, возникает проблема. В данном случае, мы вне опасности, но в коде изделия нужно быть гораздо более осмотрительным.

Строка 82 сортирует данные по имени и по ID сотрудника, а затем строки 84–91 выводят отсортированные данные. Сходным образом строка 94 пересортировывает данные, на этот раз по старшинству, а строки 97–103 выводят результаты. После компилирования и запуска программа выдает следующие результаты:

$ ch06-sortemp < presdata.txt

Sorted by name:

  Bush George 41 Fri Jan 20 13:00:00 1989

  Bush George 43 Sat Jan 20 13:00:00 2001

  Carter James 39 Thu Jan 20 13:00:00 1977

  Clinton William 42 Wed Jan 20 13:00:00 1993

  Reagan Ronald 40 Tue Jan 20 13:00:00 1981

Sorted by seniority:

  Carter James 39 Thu Jan 20 13:00:00 1977

  Reagan Ronald 40 Tue Jan 20 13:00:00 1981

  Bush George 41 Fri Jan 20 13:00:00 1989

  Clinton William 42 Wed Jan 20 13:00:00 1993

  Bush George 43 Sat Jan 20 13:00:00 2001

(Мы использовали 1 час пополудни как приблизительное время, когда все президенты начали работать.)[66]

Стоит заметить одну вещь: qsort() переставляет данные в массиве. Если каждый элемент массива представляет собой большую структуру, при сортировке массива большое количество данных будут копироваться туда-сюда. Вместо этого может оказаться выгодным создать отдельный массив указателей, каждый из которых указывает на один элемент массива. Затем использовать qsort() для сортировки массива указателей, получая доступ к несортированным данным через сортированные указатели.

Платой за это является дополнительная память для размещения указателей и модификация функций сравнения для дополнительного перенаправления указателей при сравнении структур. Полученной выгодой может стать значительное ускорение работы, поскольку на каждом шаге перемещается лишь четырех- или восьмибайтный указатель вместо большой структуры. (Наша struct employee имеет размер по крайней мере 68 байтов. При обмене четырехбайтных указателей перемещается в 17 раз меньше данных, чем при обмене структур.) Для тысяч размещенных в памяти структур разница мажет быть существенной.

ЗАМЕЧАНИЕ. Если вы являетесь программистом С++, знайте! qsort() может быть опасной для использования с массивами объектов! qsort() осуществляет простые перемещения памяти, копируя байты. Она совершенно ничего не знает о конструкциях С++, таких, как конструкторы копирования или функции operator=(). Вместо этого используйте одну из функций сортировки STL[67] или используйте методику отдельного массива указателей.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

На что обращать внимание при изучении сотрудников конкурента

Из книги Социальные сети [Источники новых клиентов для бизнеса] автора Парабеллум Андрей Алексеевич

На что обращать внимание при изучении сотрудников конкурента Специалист конкурентной разведки должен держать в поле своего зрения ключевых сотрудников компаний и учреждений, способных оказать положительное или отрицательное влияние на деятельность определенного


Стимулирование сотрудников

Из книги Язык Си - руководство для начинающих автора Прата Стивен

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


Пример 25-6. Старая, добрая: "Пузырьковая" сортировка

Из книги Поиск персонала с помощью компьютера. Как сэкономить на кадровом агентстве автора Гладкий Алексей Анатольевич

Пример 25-6. Старая, добрая: "Пузырьковая" сортировка #!/bin/bash# bubble.sh: "Пузырьковая" сортировка.# На каждом проходе по сортируемому массиву,#+ сравниваются два смежных элемента, и, если необходимо, они меняются местами.# В конце первого прохода, самый "тяжелый" элемент


ПРИМЕР: СОРТИРОВКА СТРОК

Из книги Продвижение порталов и интернет-магазинов автора Гроховский Леонид О.

ПРИМЕР: СОРТИРОВКА СТРОК      Возьмем реальную задачу сортировки строк в алфавитном порядке. Эта задача может возникнуть при подготовке списка фамилий, при создании алфавитного указателя и во многих других ситуациях. В такой программе одним из главных инструментов


Поиск сотрудников в Интернете

Из книги автора

Поиск сотрудников в Интернете Как отмечалось выше, многие кадровые агентства, не мудрствуя лукаво, выискивают своим клиентам сотрудников в Интернете – на сайтах по трудоустройству, досках бесплатных объявлений, и т. д. При этом за свои услуги такие агентства берут


Привлечение собственных сотрудников для поиска кандидатов

Из книги автора

Привлечение собственных сотрудников для поиска кандидатов В процессе поиска нового сотрудника руководитель предприятия нередко предпринимает массу усилий и несет значительные финансовые затраты ради того, чтобы максимально быстро найти квалифицированного и


Обучиться самому (или обеспечить обучение сотрудников)

Из книги автора

Обучиться самому (или обеспечить обучение сотрудников) Даже когда процедуры реагирования на инцидент имеются, системные администраторы и пользователи могут быть не обучены их применению. Политики и процедуры, которые не были ясно усвоены, не принесут много пользы. При


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

Из книги автора

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


Резюме: Не спрашивайте у сотрудников компании, отвечающих за безопасность, что они могут для вас сделать

Из книги автора

Резюме: Не спрашивайте у сотрудников компании, отвечающих за безопасность, что они могут для вас сделать Страшно видеть, что может случиться с компанией, в которой нет четко определенных ролей и обязанностей. Когда такое доходит до обеспечения безопасности, то фраза «Это


Создание контента силами сотрудников: о копирайтерах и копирайтинге

Из книги автора

Создание контента силами сотрудников: о копирайтерах и копирайтинге Под копирайтингом изначально понималась деятельность по созданию рекламных текстов. Копирайтерами называли специалистов, которые эти тексты создавали.Копирайтер в классическом понимании слова –