Сортировка с использованием стеков только для чтения

Рассмотрим следующую настройку:

• нам дан стек который содержит элементов.$s$$n$
• мы можем использовать постоянное количество дополнительных стеков .$O(1)$
• мы можем применить следующие операции к этим стекам:
  1. проверить, пуст ли стек,
  2. сравнить верхние позиции двух стеков,
  3. удалить верхний элемент в стеке,
  4. распечатать верхний элемент в стопке,
  5. скопировать верхний элемент стека в другой стек,
  6. скопировать содержимое одного стека в другой стек.

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

Вот алгоритм сортировки стеков с сравнениями:$O(n^2)$

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Можем ли мы сделать лучше?

Существует ли программа, которая печатает отсортированный список элементов в стопках, используя только $O(n\log n)$ сравнений?

Я думаю, что теперь я могу продемонстрировать нетривиальную нижнюю границу. Идея состоит в том, чтобы реализовать любую такую ​​программу с помощью семейства сравнительных ветвящихся программ. Предположение «только для чтения» означает, что наше семейство ветвящихся программ использует мало, то есть , место. Затем мы применяем нижнюю оценку S T = Ω ( n 2 ), доказанную Бородиным и соавт. в «Пространственно-временном обмене для сортировки на не забывающих машинах». Это дает нам нижнюю границу n 2 / log n для времени.$O(\log n)$$ST=\Omega(n^2)$$n^2/\log n$

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

Предположим, что наша программа регистров имеет строк кода и k регистров, X 1 , … , X k .$\ell$$k$$X_1,\dots,X_k$

Исправить . Построим программу ветвления сравнения для строк длины n следующим образом. Создайте узел для каждого кортежа ( i , d 1 , … , d k ), где 1 ≤ i ≤ ℓ и 0 ≤ d 1 , … , d k ≤ n . Идея в том, что вычисления в машине регистра соответствуют путям в программе ветвления, и мы находимся на узле ( i , d 1 , … , $n$$n$$(i,d_1,\dots,d_k)$$1\le i\le \ell$$0\le d_1 ,\dots, d_k \le n$ если мы находимся в строке i в машине регистрации, и длина строки, хранящейся в X i, равна d i . Теперь мы должны определить направленные ребра ветвящейся программы.$(i,d_1 ,\dots, d_k)$$i$$X_i$$d_i$

Если строка имеет форму$i$

если тогда перейдите к i 1, еще перейдите к i $X_u<X_v$$i_1$$i_2$

затем для всех , узел ( i , d 1 , … , d k ) помечается путем сравнения d u -го и d v -го элемента ввода, и «истинное» ребро переходит к ( i 1 , d 1 , … , d k ) и «ложное» ребро к ( i 2 , d 1 , … , d $d_1,\dots,d_k$$(i,d_1,\dots,d_k)$$d_u$$d_v$$(i_1,d_1,\dots,d_k)$ .$(i_2,d_1,\dots,d_k)$

Если строка имеет форму$i$

, перейти к строке i $X_1 \leftarrow tail(X_2)$$i'$

затем есть стрелка из любого узла в ( i ′ , d 2 - 1 , … , d k ) .$(i,d_1,\dots,d_k)$$(i',d_2-1,\dots,d_k)$

Если строка имеет форму$i$

, переход к строке i $print(head(X_u))$$i'$

затем есть стрелка из любого узла в ( i ′ , d 1 , … , d k ), которая помечена d u -ым узлом входа.$(i,d_1,\dots,d_k)$$(i',d_1,\dots,d_k)$$d_u$

Надеемся, что эти примеры проясняют, как я собираюсь построить свою программу ветвления. Когда все сказано и сделано, это разветвление программа имеет не более узлов, поэтому он имеет пространство O ( журнал N $\ell\cdot n^k$$O(\log n)$

Вы умеете считать элементы? Тогда, я думаю, есть довольно простая реализация Mergesort. Если бы вы могли поместить дополнительные символы в стек, вы могли бы решить это с помощью 3 стеков, как это:

Если у нас есть только один элемент, список уже отсортирован. Теперь предположим, что мы уже отсортировали верхнюю половину стека. Мы можем скопировать верхнюю половину (в обратном порядке) во второй стек и поместить поверх него символ разделения. Теперь у нас снова есть 3 стека (поскольку мы можем игнорировать уже отсортированные символы под символом разделения) и можем отсортировать нижнюю половину. Наконец, мы можем скопировать отсортированную нижнюю половину в третий стек в обратном порядке и объединить обе половины обратно в исходный стек.

Все операции стоят линейного времени, поэтому мы отсортировали список в $O(n \log n)$

(Обратите внимание, что нам нужны стеки размером из-за символов разделения, но это можно легко исправить с помощью другого стека)$n \log n$

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

$n-2^{\lfloor \log n\rfloor}$

$\log n$$c$$cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$$O(n \log n)$