Библиотеки
Как и в случае qsort, функция сравнения получает адреса сравниваемых значений, поэтому ключевое (искомое) значение должно иметь этот же тип; в данном примере нам пришлось создать фиктивный элемент типа Nameval для передачи в функцию сравнения. Сама функция сравнения nvcmp сравнивает два значения типа Nameval, вызывая strcmp для их строковых компонентов, полностью игнорируя численные компоненты:
Это похоже на scmp, только с тем отличием, что строки хранятся как члены структуры.
Неудобство передачи ключевого значения показывает, что bsearch предоставляет меньше возможностей, чем qsort. Хорошая многоцелевая функция сортировки занимает одну-две страницы кода, а двоичный поиск – ненамного больше, чем код для интерфейса с bsearch. Тем не менее лучше использовать bsearch, чем писать свою собственную версию. Как показывает опыт, программистам на удивление трудно написать двоичный поиск без ошибок.
В стандартной библиотеке C++ имеется обобщенная функция sort, которая обеспечивает время работы 0(n log n). Код для ее вызова проще, потому что нет необходимости в преобразовании типов и размеров элементов. Кроме того, для порядковых типов не требуется задавать функцию сравнения:
int arr[N]; sort(arr, arr+N);
Эта библиотека содержит также обобщенные функции двоичного поиска, с теми же преимуществами в вызове.
Упражнение 2.1
Алгоритм быстрой сортировки проще всего выразить рекурсивно. Реализуйте его итеративно и сравните две версии. (Хоар рассказывает, как было трудно разработать итеративный вариант быстрой сортировки и как легко все оказалось, когда он сделал ее рекурсивной.)