Попытка понять "LibrarySort"?

Question

Я читаю "Insertion Sort is O(nlogn) by Michael A. Bender , Martín Farach-Colton , Miguel Mosteiro", и я не совсем понимаю, как работает алгоритм и как его реализовать, даже с помощью Wikipedia. Ниже приведено описание алгоритма, извлеченного из оригинальной статьи.

1) Пусть A является массивом n-элементов для сортировки. Эти элементы вставляются один в время в случайном порядке в сортировочный массив S размера (1 + ε) n.

Итак, первый шаг - создание массива размера (1 + ε) n. Пусть ε = 1, тогда мне нужно создать массив с удвоенным размером исходного массива.

2) Вставки выполняются в журнальных циклах (n) следующим образом. Каждый раунд удваивает количество элементов, вставленных в S, и удваивает префикс S, где находятся элементы.

Я понимаю, что будет внешний цикл, который будет циклически регистрировать время (n). В каждом раунде мне нужно удвоить количество элементов из A (исходный массив) до массива S. То, что я действительно не понимаю, это «двойной префикс S».

3) В частности, круглый я ^я заканчивается, когда элемент 2 ^я вставляется и элементы балансировки. Перед перебалансировкой элементы 2 ⁱ находятся в первых положениях (1 + ε) 2 ⁱ. Перебалансировка перемещает их в первую (2 + 2ε) 2 ⁱ позиции, распространяя элементы как можно более равномерно. Мы называем 2 + 2ε коэффициентом распространения.

От этого я понимаю, что за каждый раунд мы будем выполнять «перебалансировку». «rebalance» будет равномерно распространять исходный элемент в массиве S, чтобы он оставил некоторый промежуток между элементами. Формула для распространения элемента является: к = я * (1 + ε), где я старый индекс и к является новый индекс.

4) Вставка 2 ^I-1 вставочных элементов в раунде я ^я выполняется в переборе пути: поиск целевого положения элемента, чтобы быть вставленной двоичного поиска (среди 2 ^i-1 опорных позиций в S) и перемещать элементы высшего ранга, чтобы освободить место для нового элемента. Не все элементы более высокого ранга необходимо перенести, только те, что находятся в соседних позициях массива, до ближайшего разрыва.

В этой части показано, как вставить каждый элемент в массив S. Во-первых, используйте двоичный поиск для поиска, где должен принадлежать элемент. Затем сдвиньте более высокий ранг, пока он не достигнет пробела.

Это перевод алгоритма из того, что я понимаю (где А массив для сортировки и массива начинаются с индексом 1):

 
def LibrarySort(A) 
    n ← length(A) 
    S ← array of size (1 + ε) * n 

    for i ← 1 to n 
     S[i] = null 

    for i ← 1 to floor(log(n) + 1) 
     for j ← 2i - 1 to 2i 
      index = binarysearch(S, A[j]) 
      insert(S, A[j], index) 
     rebalance() 

Тогда для вставки() принимает 3 параметра: массив, элемент для вставки и местоположение.

def insert(S, item, index) 
    if S[index] != null 
     tmp ← S[index] 
     i ← index + 1 
     while i <= length(S) and S[i] != null 
      swap(tmp, S[i]) 
      i++ 
    S[index] ← item 

Вопросы

• Это то, что я понимаю правильно?
• Что такое "double prefix of S"?

Answer 1

объявления «удвоить префикс S»: Массив (память) выделяется один раз в начале до размера (1 + ε) п, где п является общее количество элементов для сортировки. Но элементы добавляются постепенно, и по мере их добавления они не распространяются по всему массиву, а только на некоторый префикс. При м элементов перебалансированы, они распределены по первому (1 + ε ) м элементов массива. Это префикс. Когда m удваивает, то есть (1 + ε) m.

правильность объявления: Я вижу одну небольшую ошибку:

формула для распространения элемента является: к = я * (1 + ε), где я старый индекс, а к новый индекс.

В приведенном ниже описании не указано, что такое формула, но она не может быть такой. Потому что это будет карта массив длиной м к длине (1 + ε) м, но описание говорит, что вы картирование массив длины (1 + ε) м массиву длины 2 (1 + ε) m.

простое выражение будет к = 2 я где я является старым индекса, но это не будет распространяться элементами равномерно. Для того, чтобы равномерно распределить элементы, формула к = (2 + 2 ε) я, но я является индексом за исключением каких-либо зазоров.