При внедрении Sorting Sort, двоичный поиск может использоваться для определения местоположения в первых элементах i-1 массива, в которые должен быть вставлен элемент i.
Как это повлияет на количество сравнений? Как бы использование такого бинарного поиска повлияло на асимптотическое время работы для сортировки вставки?
Я уверен, что это уменьшит количество сравнений, но я не совсем уверен, почему.
Прямо из Википедии:
Если стоимость сравнений превышает стоимость свопов, как это имеет место например, со строковыми ключами, хранящимися по ссылке или с человеческим взаимодействие (например, выбор одной из пары, отображаемой бок о бок), то использование двоичной сортировки вставки может повысить производительность. Binary inserting использует двоичный поиск для определения правильного местоположение для вставки новых элементов и, следовательно, выполняет ⌈log2 (n) ⌉ сравнения в худшем случае, который является O (n log n). Алгоритм как у целого все еще есть время работы O (n2) в среднем из-за серии свопов, необходимых для каждой вставки.
Источник:
http://en.wikipedia.org/wiki/Insertion_sort#Variants
Вот пример:
http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html
Я уверен, что это уменьшит количество сравнений, , но я не совсем уверен, почему.
Хорошо, если вы уже знаете сортировку вставки и бинарный поиск, то это довольно прямолинейно. Когда вы вставляете кусок в сортировке вставки, вы должны сравнивать все предыдущие части. Скажите, что вы хотите переместить этот [2] в нужное место, вам придется сравнить с 7 частями, прежде чем вы найдете нужное место.
[1] [3] [3] [3] [4] [4] [5] → [2] - [11] [0] [50] [47 ]
Однако, если вы начнете сравнение на половине пути (например, двоичный поиск), вы сравните только 4 штуки! Вы можете сделать это, потому что знаете, что левые части уже в порядке (вы можете делать только двоичный поиск, если штуки в порядке!).
Теперь представьте, если бы у вас были тысячи штук (или даже миллионы), это сэкономит вам много времени. Надеюсь, это поможет. | = ^)
Если у вас хорошая структура данных для эффективного бинарного поиска, вряд ли будет установлено время ввода O (log n). И наоборот, хорошая структура данных для быстрой вставки в произвольном положении вряд ли поддержит двоичный поиск.
Для достижения производительности O (n log n) наилучшего сравнения с сортировкой вставки потребуется как двоичный поиск O (log n), так и O (log n).
Предполагая, что массив отсортирован (для выполнения бинарного поиска), он не уменьшит никаких сравнений, так как внутренний цикл заканчивается сразу после 1 сравнения (поскольку предыдущий элемент меньше). В общем случае количество сравнений в сортировке вставки равно максимальному числу инверсий плюс размер массива - 1.
Так как число инверсий в отсортированном массиве равно 0, максимальное количество сравнений в уже отсортированном массиве равно N - 1.
Binary Insertion Sort - Возьмите этот массив => {4, 5, 3, 2, 1}
Теперь внутри основного цикла представьте, что мы находимся на третьем элементе. Теперь с помощью бинарного поиска мы будем знать, куда вставить 3, т.е. до 4.
Бинарный поиск использует сравнение O (Logn), что является улучшением, но нам все еще нужно вставить 3 в нужном месте. Для этого нам нужно поменять 3 с 5, а затем с 4.
Из-за того, что вставка занимает столько же времени, сколько и без бинарного поиска, в худшем случае сложность все равно остается O (n ^ 2). Надеюсь, это поможет.