В стандартные библиотеки языков С и C++ входят функции сортировки, которые устойчивы к неблагоприятным входным данным и настроены на предельно быструю работу.
Библиотечные функции написаны так, что они могут сортировать данные любого типа, но мы в свою очередь должны адаптироваться к их интерфейсу, что может быть несколько сложнее, чем в рассмотренном выше примере. В языке С библиотечная функция называется qso rt, и ей нужно предоставлять функцию сравнения двух значений. Поскольку значения могут быть любых типов, то функции сравнения передаются два нетипизированных указателя (void *) на сравниваемые значения. Функция преобразует указатели к нужному типу, извлекает значения данных, сравнивает их и возвращает результат (отрицательный, нуль или положительный в зависимости от того, меньше ли первый элемент, равен ли второму или больше его).
Рассмотрим реализацию функции сравнения для сортировки массива строк, случая, встречающегося довольно часто. Мы написали функцию scmp, которая -преобразует параметры к другому типу и затем вызывает st rcmp для выполнения самого сравнения:
/* scmp: сравнение строк *р1 и *р2 */
int scmp(const void *p1, const void *p2)
{
char *v1, *v2;
v1 = *(char **) p1; v2 = *(char **) p2;
return strcmp(v1, v2); }
Мы могли бы написать эту функцию в одну строку, но при использовании временных переменных код становится более удобочитаемым.
Мы не можем напрямую использовать strcmp как функцию сравнения, поскольку qsort передает адрес каждого элемента в массиве &s t г [ i ] (типаспаг **), ане str[i] (типа char *), как показано на рисунке:
Для сортировки элементов массива строк с st r[0] по st r[N-1 ] функция qsort должна получить массив, его длину, размер сортируемых элементов и функцию сравнения:
char *str[N];
qsort(str, N, sizeof(str[OJ), scmp);
А вот аналогичная функция icmp для сравнения целых:
{
int v1, v2;
v1 = *(int *) p1; v2 = *(int *.) p2;
if (v1 < v2)
return -1; else
if (v1 == v2)
return 0; else
return 1; >
}
Мы могли бы написать
? return v1-v2;
но если v2 — большое положительное число, a v1 — большое по абсолютному значению отрицательное или наоборот, то получившееся переполнение привело бы к неправильному ответу. Прямое сравнение длиннее, но надежнее.
И здесь при вызове qsort нужно передать массив, его длину, размер сортируемых элементов и функцию сравнения:
int arr[N];
qsort(arr, N, sizeof(arr[0]), icmp);
В стандарте ANSI С определена также функция двоичного поиска bsea rch. Как и qso rt, этой функции нужен указатель на функцию сравнения (часто на ту же, что используется для qsort); bsearch возвращает указатель на найденный элемент или на NULL, если такого элемента нет. Вот наша программа для поиска имен в HTML-файле, переписанная с использованием bsearch:
/* lookup: использует bsearch для поиска name в таблице tab,
возвращает индекс */
int lookup(char *name, Nameval tab[],
int ntab) {
Nameval key, *np;
key.value = 0; /* не используется;
годится любое значение */
np = (Nameval *) bsearch(&key, tab, ntab,
sizeof(tab[0]), nvcmp); if (np == NULL)
return -1; else
return np-tab;
Как и в случае qsort, функция сравнения получает адреса сравниваемых значений, поэтому ключевое (искомое) значение должно иметь этот же тип; в данном примере нам пришлось создать фиктивный элемент типа Nameval для передачи в функцию сравнения. Сама функция сравнения nvcmp сравнивает два значения типа Nameval, вызывая st rcmp для их строковых компонентов, полностью игнорируя численные компоненты:
/* nvcmp: сравнивает два вначения типа
Nameval */
int nvcmp(const void *va, const void *vb)
{
const Nameval *a, *b;
a = (Nameval *) va;* b = (Nameval *) vb;
return strcmp(a->name, b->name); }
Это похоже на scmp, только с тем отличием, что строки хранятся как члены структуры.
Неудобство передачи ключевого значения показывает, что bsearch предоставляет меньше возможностей, чем qso rt. Хорошая многоцелевая функция сортировки занимает одну-две страницы кода, а двоичный поиск — ненамного больше, чем код для интерфейса с bsearch. Тем не менее лучше использовать bsearch, чем писать свою собственную версию. Как показывает опыт, программистам на удивление трудно написать двоичный поиск без ошибок.
В стандартной библиотеке C++ имеется обобщенная функция sort, которая обеспечивает время работы 0(п log n). Код для ее вызова проще, потому что нет необходимости в преобразовании типов и размеров элементов. Кроме того, для порядковых типов не требуется задавать функцию сравнения:
int arr[N]; sort(arr, arr+N);
Эта библиотека содержит также обобщенные функции двоичного поиска, с теми же преимуществами в вызове.
Упражнение 2-1
Алгоритм быстрой сортировки проще всего выразить рекурсивно. Реализуйте его итеративно и сравните две версии. (Хоар рассказывает, как было трудно разработать итеративный вавариант быстрой сортировки и как легко все оказалось, когда он сделал ее рекурсивной.)
