Улучшение времени выполнения сортировки вставки с использованием бинарного поиска - PullRequest
Новая
       21

Улучшение времени выполнения сортировки вставки с использованием бинарного поиска

2 голосов
/ 27 февраля 2012

Цикл while использует линейный поиск для сканирования в обратном направлении. Однако мы знаем, что массив в цикле while уже отсортирован. Таким образом, мы можем заменить линейный поиск на бинарный поиск, так что O (n) изменится на O (lg n). Тем не менее, я считаю, что это не будет способствовать сокращению общего времени, потому что нам все равно придется перемещать элементы на один индекс вперед, что всегда будет проходить (количество шагов назад (n)) раз. Таким образом, в целом время выполнения остается O (n ^ 2), и нет никакого способа достичь O (n lg n) для этого случая. Пожалуйста, скажите мне, если я подхожу к этому неправильно. 

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key

Ответы [ 4 ]

5 голосов
/ 27 февраля 2012

сортировка вставок помещает элементы массива, чтобы освободить место для следующего элемента в строке.
поэтому, если вы найдете место для ввода нового элемента с помощью бинарного поиска, вам все равно нужно будет подтолкнуть все элементы после этого индекса на один шаг вперед (вправо).
с учетом массива, отсортированного в обратном направлении: 10,9,8,7,6,5,4,3,2,1
вам нужно будет нажать i-1 вправо, чтобы вставить i-й элемент (даже если вы используете бинарный поиск) - время наихудшего случая: O (n ^ 2)
если бы вы могли вставлять элементы один за другим в список, вам не нужно было бы выдвигать эти элементы, но вам придется «платить» за поиск правильного местоположения в списке (поэтому в этой реализации WCT - это O (п ^ 2)).

решение этой проблемы будет заключаться в некотором взаимодействии между списками и массивами, чтобы вы могли достичь i-го элемента за O (1) времени (как в массивах) и могли вытолкнуть новый элемент в заданное место ( скажем после индекса j) в O (1) раз (как в списках) - если вы добьетесь успеха, я верю, что вы выиграете вечную славу!

0 голосов
/ 27 февраля 2012

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

0 голосов
/ 27 февраля 2012

Как правило, время, необходимое для сортировки вставкой, состоит из трех факторов:

  1. Перебирая каждый элемент в массиве SOURCE
  2. Нахождение правильного места для его вставки вМассив DESTINATION
  3. Выполнение вставки.

То, о чем вы говорите, касается шага 2. Наивным способом было бы пройти через весь массив DESTINATION, чтобы найти место вставки, которое занимаетO(n).Тем не менее, вы можете выполнить бинарный поиск, который займет у вас всего лишь O(log(n)).

. Вам все равно нужно будет выполнить вставку, но стоимость этого зависит от структуры данных.Если вы используете связанный список, он всегда будет занимать у вас постоянное количество времени.Если вы используете простой массив, вы можете просто сделать memcpy(), который должен одинаково хорошо масштабироваться.Подход, который вы используете в псевдокоде, является очень наивным и никогда не будет действительным в реальной реализации.См. http://www.docjar.com/html/api/java/util/ArrayList.java.html#421 для реального примера INSERT для массивов.System.arraycopy() - это O(1).

0 голосов
/ 27 февраля 2012

Я думаю, что время выполнения равно O (nlgn) .. бинарный поиск занимает время lgn ... а перемещение элементов занимает O (n / 2) в худшем случае, что «асимптотически одинаково» как O (n) [Я не могу найти символ «принадлежит» ..: D]

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

...