Какую сортировку применить для слов и чисел?

Question

[Максим]

Символов на входе не более 5000. В алгоритмах не силен(временно) и нужен совет какую сортировку использовать.

Пример:

Input:
car truck 8 -4 bus 6 1
Output:
bus car -4 1 truck 6 8

Должен сохраняться порядок чисел и слов при сортировке.

Comments

[sim3x]

Откуда такой лист берется?

[Максим]

sim3x, stdin, считать что данные валидны

[Mercury13]

Огласите полную задачу.

[Mercury13]

Похоже на сортировку строк (−4 = «minus four»), но из этого правила выпадает eight.

Answer 1

[Владимир Олохтонов]

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

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

Comments

[Максим]

Можно сделать и так, но желательно использовать алгоритм сортировки чисел и символов чтобы уменьшить время затрачиваемое на определение индексов циклом for

[Владимир Олохтонов]

Максим, у вас 1 проход по всей последовательности для считывания и сохранения индексов, это O(n), затем сортировка слов и чисел, это O(nlogn).

От того, что вы сначала прочитаете все 5к элементов, асимптотика решения не изменится.