Всем привет.

Есть массив, состоящий из перемешанных пар городов (отправление и прибытие) вида
[E, C], [B, D], [C, A], [F, E], [A, B]

Подскажите, пожалуйста, какой лучше использовать алгоритм сортировки, чтобы отсортировать города по порядку движения поезда (весь маршрут):

[F, E] -> [E, C] -> [C, A] -> [A, B] -> [B, D]

берете первую пару,
пытаетесь к ней присоединить вторую справа или слева, потом третью и т.д.
дошли до последней пары, попытались присоединить
если остались неприсоединенные пары, пробуем снова присоединить

как-то так, например

Отсортируй быстрым сортом по отправлению. После чего в один проход пересобери по стыковкам.

Lipetsk, а если допустим, у меня получилось к первой паре присоеденить третью, то что я дальше делаю? Пытаюсь присоеденить четвёртую к третьей или к первой?


Akina, не понял, отсортировать отправления просто бинарной сортировкой по алфавиту?
А как затем я смогу за один проход расставить все по местам? Распиши плз поподробнее, у меня туговато с матчастью 

Вообще, я пока сделал так:
Беру первую пару (отрезок пути) дальше среди оставшихся ищу следующий отрезок, вырезаю и вставляю за ним. Дальше ищу следующего для него начиная уже с третьего элемента и так далее, пока не дойду до конечного отрезка. После этого меняю направление и ищу среди оставшихся неотсортированными элементов предшествующие отрезки, вырезаю и вставляю их в начало массива.
Ничего умнее придумать не смог. Если кто знает, подскажите как можно улучшить и этот алгоритм, просто мне нужно понять как мыслить  Еще, скажите какая алгоритмическая сложность у моего и у ваших примеров. Большое спасибо!

Это сообщение отредактировал(а) Alx - 26.3.2011, 03:34

т.е. хочешь сказать пару [F, E] невозможно присоединить и поэтому эта пара должна быть начальной точкой отправления.

Добавлено через 5 минут и 46 секунд


присоединяй сразу с двух сторон. так автоматически найдешь начало отправления и конец

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

 берем первую пару [E,C] пытаемся присоединить со второй парой. если вторую пару нельзя присоединить создаем вторую ленту(список) и третью, четвертую, пятую и т.д. пару будем пытаться присоединить к первой и второй паре,т.е. к той которая  присоединиться. 
Если третья пара тоже не сможет присоединиться, то создаем третью ленту(список).
 т.е будет работать примерно так: 
выбираем элемент [Е,С] -создаем первую ленту в ней пока один элемент
____________________
                       [B, D]- создаем вторую, третью и т.д. лент(столько сколько понадобиться)
первый шаг    [Е,С] - первая лента
____________________
                       [B, D]
второй шаг    [Е,С][C, A] - начинаем "наращивать" ленты
___________________________
                       [B, D]
третий шаг    [F, E][Е,С][C, A]
______________________

                          [A, B] [B, D]
четвертый шаг [F, E][Е,С][C, A]
__________________________
а потом просто соединяем концы полученных лент [F, E][Е,С][C, A][A, B] [B, D]


                        

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

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

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

Добавлено через 2 минуты и 13 секунд
но скорей всего в большинстве случаев замедлит работу программы

миг, Правильно ли я понял, что формируются ВООБЩЕ ВСЕ возможные маршруты (ленты). И только потом из всех лент магическим образом выбирается нужная?
Imho, при большом количестве маршрутов - эффективнее присоединять от одной из точек с одной стороны. Меньше вариантов для перебора.

ksnk, почитайте исходное условие. Имеется ОДИН маршрут, разбитый на участки. И его надо собрать обратно. Поэтому конечное состояние - всегда одна лента, включающая все участки. Если не так - исходные данные неверны.


Зачем? это происходит автоматически:

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

кажется вы правы. просто была мысль, что допустим  данные расположены крайне не удачно.
например так [Е,С][A, B] [X,Z][M,P][z,M][D,X][F, E][B, D][C, A]
то у нас в самом начале получиться четыре не связаные ленты

и на 5 шаге элемент [z,M] нужно сравнить с четырьмя лентами. т.е.  чем больше лент тем больше сравнений.  поэтому и решил, что на каком то этапе логичнее объединять ленты..  вероятность такого неудачного расположения данных на мой взгляд довольно низкая.. Так, что для данного примера в большинстве случаев, при перемешивании входных данных,   будет создаваться меньше 4 лент.