До сих пор мы сортировали только массивы символов. Очевидно, что приведенные выше функции можно переделать для сортировки массивов любого из встроенных типов данных, просто поменяв типы параметров и переменных. Тем не менее, обычно возникает необходимость сортировать составные типы данных, например строки, или агрегированные данные, например структуры. Большинство задач сортировки имеют дело с ключом и информацией, связанной с этим ключом. Чтобы адаптировать алгоритмы для обработки подобных данных, необходимо модифицировать код сравнения, код обмена или оба фрагмента. Сам алгоритм при этом не меняется.
Поскольку быстрая сортировка в настоящее время является одним из лучших методов сортировки общего назначения, она используется в последующих примерах. Тем не менее, тот же принцип относится и ко всем остальным методам, описанным ранее.
Сортировка строк является распространенной задачей программирования. Строки легче всего сортировать, когда они хранятся в таблице строк. Таблица строк — это просто массив строк. А массив строк — это двумерный массив символов, в котором количество строк в таблице определяется размером левого измерения, а максимальная длина строки — размером правого измерения. (О массивах строк рассказывалось в главе 4.) Нижеследующая строковая версия быстрой сортировки принимает массив строк, в котором размер каждой строки ограничен десятью символами. (Можете изменить эту длину, если хотите.) Данная версия сортирует строки в лексикографическом порядке.
/* Быстрая сортировка строк. */
void quick_string(char items[][10], int count)
{
qs_string(items, 0, count-1);
}
void qs_string(char items[][10], int left, int right)
{
register int i, j;
char *x;
char temp[10];
i = left; j = right;
x = items[(left+right)/2];
do {
while((strcmp(items[i],x) < 0) && (i < right)) i++;
while((strcmp(items[j],x) > 0) && (j > left)) j--;
if(i <= j) {
strcpy(temp, items[i]);
strcpy(items[i], items[j]);
strcpy(items[j], temp);
i++; j--;
}
} while(i <= j);
if(left < j) qs_string(items, left, j);
if(i < right) qs_string(items, i, right);
}
Обратите внимание, что во фрагменте сравнения теперь используется функция strcmp(). Эта функция возвращает отрицательное число, если первая строка лексикографически меньше второй, возвращает ноль, если строки равны, и положительное число, если первая строка лексикографически больше второй. Также следует отметить, что для обмена двух строк требуется три вызова функции strcpy().
Имейте в виду, что функция strcmp() замедляет сортировку по двум причинам. Во-первых, в программе появляется вызов функции, что всегда отнимает время. Во-вторых, сама функция strcmp() выполняет несколько сравнений, чтобы определить, какая из двух строк больше. В первом случае, если скорость очень важна, можно поместить код сравнения строк непосредственно в функцию сортировки, продублировав код функции strcmp(). Во втором случае нет никакого способа избежать сравнения строк, поскольку по определению это именно то, что требуется в данной задаче. Те же рассуждения относятся и к функции strcpy(). Обмен двух строк с помощью strcpy() включает в себя вызов функции и посимвольный обмен содержимого строк — каждая из этих операций занимает время. Накладные расходы на вызов функции можно устранить, вставив код копирования прямо в алгоритм сортировки. Однако тот факт, что обмен двух строк означает обмен отдельных символов (один за другим), изменить невозможно.
Ниже приведена простая функция main(), демонстрирующая работу функции быстрой сортировки строк quick_string():
#include <stdio.h>
#include <string.h>
void quick_string(char items[][10], int count);
void qs_string(char items[][10], int left, int right);
char str[][10] = { "один",
"два",
"три",
"четыре"
};
int main(void)
{
int i;
quick_string(str, 4);
for(i=0; i<4; i++) printf("%s ", str[i]);
return 0;
}
В большинстве прикладных программ, в которых используется сортировка, предусмотрена сортировка совокупностей данных. Например, списки почтовой рассыпки, складские базы данных и журналы сотрудников содержат наборы разнотипных данных. Как вам известно, в программах на языке С совокупности данных обычно хранятся в структурах. Хотя структура обычно содержит несколько членов, структуры, как правило, сортируются только по одному полю-члену, который используется в качестве ключа сортировки. За исключением выбора ключа, приемы сортировки структур ничем не отличаются от приемов сортировки других типов данных.
Чтобы проиллюстрировать пример сортировки структур, давайте создадим структуру под называнием address, в которой можно хранить почтовый адрес. Подобная структура может применяться в программе почтовой рассылки. Описание структуры address показано ниже:
struct address {
char name[40]; /* имя */
char street[40]; /* улица */
char city[20]; /* город */
char state[3]; /* штат */
char zip[11]; /* индекс */
};
Поскольку представляется разумным организовать список адресов в виде массива структур, в данном примере предположим, что процедура сортировки будет сортировать массив структур типа address. Такая процедура показана ниже. Она сортирует адреса по почтовому индексу.
/* Быстрая сортировка структур типа фвкуыы. */
void quick_struct(struct address items[], int count)
{
qs_struct(items,0,count-1);
}
void qs_struct(struct address items[], int left, int right)
{
register int i, j;
char *x;
struct address temp;
i = left; j = right;
x = items[(left+right)/2].zip;
do {
while((strcmp(items[i].zip,x) < 0) && (i < right)) i++;
while((strcmp(items[j].zip,x) > 0) && (j > left)) j--;
if(i <= j) {
temp = items[i];
items[i] = items[j];
items[j] = temp;
i++; j--;
}
} while(i <= j);
if(left < j) qs_struct(items, left, j);
if(i < right) qs_struct(items, i, right);
}