У нас есть стек, содержащий N элементов.
Мы извлекаем один элемент из стека и добавляем его в память ( лента Тьюринга ).
Какой самый оптимальный способ (наименьшее количество операций) сохранить список отсортированным по свойству one свойству объектов?
Мое текущее решение является самым простым в реализации и будет служить примером:
1. Начальное состояние
Stack: [ 3,1,2]
temp memory: []
TapeIndex: []
tape : []
2.
Вставьте стопку, сохраните ее на ленту
Stack: [1,2]
TapeIndex: [0]
tape : [3]
Если лента отсортирована, мы переходим к следующей
3.
Мы снова всплываем. Мы проверяем, является ли самое низкое значение индекса ниже нашего числа. Если да, мы перемещаем ** ВСЕ значения ** на одно влево.
Stack: [2]
temp memory: [1]
TapeIndex: [0 ,1]
tape : [null,3]
затем мы добавляем его в форт.
Stack: [2]
temp memory: [1]
TapeIndex: [0,1]
tape : [1,3]
4.
Мы добавляем еще один элемент.
Stack: []
temp memory: [2]
TapeIndex: [0,1]
tape : [1,3]
Мы проверяем если значение индекса lowets меньше (это не так, поэтому мы двигаемся далеко) Secon самое низкое значение индекса меньше. так что я переместил все вышеуказанные значения вверх
Stack: []
temp memory: [2]
TapeIndex: [0,1 ,2]
tape : [1,null,3]
и добавил его на место.
Stack: []
temp memory: []
TapeIndex: [0,1,2]
tape : [1,2,3]
Заключение
Мой метод вообще не задействован, и количество операций, выполняемых на ленте, растет с увеличением размера ленты.
Я ищу любое решение, которое лучше моего.
Спасибо за все сообщения, используйте комментарии, чтобы получить больше информации.