Самый быстрый способ перевернуть список? (Только смежные элементы могут быть заменены)
Это теоретический / математический вопрос. Может быть, кто-то найдет применение для этого, хотя.
Я переставлял некоторые слои в Inkscape, пытаясь перевернуть весь стек, и мне было интересно, каков был бы самый быстрый (т.е. наименее перемещающийся) способ перевернуть список, учитывая ограничение, что вы можете поменять местами только два смежных элемента за раз.
Самый простой способ - это что-то похожее на пузырьковую сортировку:
a, b, c, d, e, f -> b, a, c, d, e, f -> b, c, a, d, e, f -> b, c, d, a, e, f ->... -> f, e, d, c, b, a
Но есть ли более быстрый способ?
2 ответа
Нет, я думаю, что у вас меньше всего свопов. Вы должны выполнить пять, чтобы получить a до конца, затем еще четыре, чтобы получить b до второй с последней позиции и так далее.
Любой другой обмен сделан во время движения a не приведет к a все ближе.
Отсюда минимальный счет свопа для {a, b, c, d, e, f} является 5 + 4 + 3 + 2 + 1, Это примерно так же эффективно, как пузырьковая сортировка, поэтому, вероятно, ее следует избегать для любых приличных данных. Тем не менее, даже пузырьковая сортировка в порядке, если размеры данных достаточно малы, чтобы никто не заметил.
Мне кажется, что если ваш домен Inkscape, у вас не будет на самом деле особенно большого количества слоев. Для более общего домена, вы должны сосать его и посмотреть:-)
Самый быстрый способ - пройти по тому же списку от последнего элемента к первому. Никаких свопов вообще.