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

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

 
 

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

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

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

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

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

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

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

Таким образом, число сравнений ключей при сортировке удовлетворяет неравенству

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

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

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