Вставка Сортировка с двоичным поиском

Question

При внедрении Сортировка вставки двоичный поиск может быть использован для определения местоположения в первых элементах i-1 массива, в которые должен быть вставлен элемент i.

Как это повлияет на количество сравнений? Как использование такого бинарного поиска повлияет на асимптотическое время работы для сортировки вставки?

Я уверен, что это уменьшит количество сравнений, но я не совсем уверен, почему.

Answer 1

Прямые из Википедии:

Если стоимость сравнений превышает стоимость свопов, как это имеет место , например, с строковыми ключами, хранящихся в виде ссылки, или с человеческим взаимодействия (например, выбирая один из А пара, отображаемая бок о бок), , тогда использование двоичной сортировки вставки может повысить производительность. Двоичный вставки использует своего рода двоичный поиск, чтобы определить правильное расположение для вставки новых элементов, и, следовательно, выполняет ⌈log2 (п) ⌉ сравнений в худшем случае, который является О (п п) войти. Алгоритм как целое все еще имеет время работы O (n2) в среднем из-за серии сводок , необходимых для каждой вставки.

Источник:

http://en.wikipedia.org/wiki/Insertion_sort#Variants

Вот пример:

http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html

Я уверен, что это уменьшит количество сравнений, но я m не совсем уверен, почему.

Ну, если вы знаете сортировку вставки и бинарный поиск уже, то ее довольно прямолинейно. Когда вы вставляете кусок в сортировке вставки, вы должны сравнивать все предыдущие части. Скажите, что вы хотите переместить этот [2] в нужное место, вам придется сравнить с 7 частями, прежде чем вы найдете нужное место.

[1] [3] [3] [3] [4] [4] [5] ->[2] < - [11] [0] [50] [47]

Однако, если вы начнете сравнение на половине пути (например, двоичный поиск), вы сравните только 4 штуки! Вы можете сделать это, потому что знаете, что левые части уже в порядке (вы можете делать только двоичный поиск, если штуки в порядке!).

Теперь представьте, если бы у вас было тысячи штук (или даже миллионов), это сэкономит вам много времени. Надеюсь, это поможет. | = ^)

Answer 2

Если у вас хорошая структура данных для эффективного двоичного поиска, то вряд ли у вас будет время ввода O (log n). И наоборот, хорошая структура данных для быстрой вставки в произвольной позиции вряд ли поддерживает двоичный поиск.

Для достижения наилучших результатов поиска с сортировкой входов (n log n) потребуется как двоичный поиск O (log n), так и O (log n).

Answer 3

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

Поскольку число инверсий в отсортированном массиве равно 0, максимальное количество сравнений в уже отсортированном массиве равно N - 1.