Лексикографическая сортировка

Задача:

Пусть имеется N строк различной длины алфавита мощности M с заданным на них лексикографическим порядком (см. [3,4,9,12]). Необходимо отсортировать их в соответствии с этим порядком, т.е. отсортировать, используя алгоритм лексикографической сортировки. Данная сортировка относится к классу распределяющих сортировок и имеет линейную трудоемкость относительно числа сортируемых строк при условии, что M<

Указания:

При реализации данного алгоритма для хранения данных следует использовать структуру данных очередь. В начале создается очередь, в которую записываются все сортируемые строки. Далее формируются M вспомогательных очередей по числу символов в алфавите. Если, например, в текущей рассматриваемой строке i-ый символ равен “a”, то данная строка размещается в очередь, соответствующую символу “a”. Просмотр символов в строке производится справа налево. Перед началом работы основного цикла алгоритма строки разбиваются по длинам. Сортировка начинается со строк большей длины.

________________________________________ ________________________________________ ________________________




Такая вот печаль, задачу целой компании в 3 человека решить не можем, ничего не понятно, глухо как в танке. Помогите кто чем может. Сдавать в сентябре, а еще конь не валялся.

0

Сообщение от Bellfator (см. [3,4,9,12])

поясните, что здесь имеется ввиду.

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.

0

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

0

Сообщение от salam поясните, что здесь имеется ввиду. Добавлено через 6 минут если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.

Задание как раз таки выглядит так, цифры, нам не понятны, но это вроде как Лексикографический порядок, даже препод незнает как сделать

0

Bellfator, http://ru.wikipedia.org/wiki/%... 0%BA%D0%B0
тут есть применение для строк, не оно?

0

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

0