Void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int (*fcmp)(const void *a, const void *b ));

Аргументы:

• key – адрес записи, имеющей структуру такую же, как и запись таблицы. В этой записи заполнены только поля, составляющие ключ.

• base – адрес начала таблицы

• nelem – число записей в таблице

• width – длина записи в байтах

• fcmp – функция, определяемая пользователем, которая сравнивает ключи записей, имеющих адреса a и b и возвращает –1 (*a<*b), 0(*a==*b) и 1(*a>*b).

Функция bsearch возвращает адрес найденной записи или NULL.

Для поиска в сортированной таблице могут быть использованы любые методы решения уравнения Ключ=F(Адрес), в частности метод золотого сечения и интерполяционные методы.

9.2.2. Вставка и удаление в сортированной таблице

П ри вставке новой записи в сортированной таблице, требуется найти место в которое её следует поместить (время ~ ) и сдвинуть все записи от места вставки и ниже на одну позицию вниз. Аналогично, при удалении требуется найти удаляемую запись и все записи ниже удаляемой сдвинуть на одну позицию вверх. Обе операции требуют физического перемещения в среднем записей. Таким образом, при таком простодушном поведении, мы проигрываем все преимущества сортированной таблицы для операции поиска. Поэтому при удалении запись не удаляют физически, а лишь помечают как удаленную в специально отведенном байте. При вставке находят ту позицию, в которую следовало бы поместить новую запись, чтобы она не нарушала порядка, но не помещают ее туда, а помещают в линейный список,

начинающийся с позиции вставки, как на рис.31.

Рис.31. Сортированная таблица с цепочками переполнения

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

9.2.3. Оценка трудоемкости сортировки !!!!!

Оценим трудоемкость процесса упорядочения массива из N ключей. В исходном состоянии эти ключи могут образовывать любую из N! перестановок. Энтропия массива ключей, определяемая по Шеннону:

где p_i – вероятность перестановки с номером i. Наибольшей энтропией обладает система, для которой все состояния равновероятны: . Для упорядоченной таблицы, все ключи которой различны, энтропия равна нулю. Изменение энтропии равно количеству информации, получаемой в процессе сортировки. Для случайного массива необходимо получить бит информации. При сравнении ключей K_i, K_j можем получить два исхода: K_i<K_j и K_i>K_{j .} (случаем К_i=K_j пренебрегаем, как маловероятным).

Если исходы равновероятны, то сравнение дает ровно 1 бит информации. Такие ключи называют статистически эквивалентными. Если исходы неравновероятны, то будет получено меньше одного бита информации. Кстати, именно из-за того, что некоторые сортировки сравнивают статистически неэквивалентные ключи, они имеют низкую эффективность. Таким образом, число сравнений ключей при сортировке удовлетворяет неравенству

Для вычисления N! воспользуемся формулой Стирлинга

С учетом этого после преобразований получим

Найденная оценка будет служить ориентиром при оценке эффективности различных методов сортировки.