Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
Bellfator
0 / 0 / 0
Регистрация: 15.04.2013
Сообщений: 17
12.08.2013, 03:40     Лексикографическая сортировка #1
Задача:

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

Указания:

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

________________________________________________________________________________________________________




Такая вот печаль, задачу целой компании в 3 человека решить не можем, ничего не понятно, глухо как в танке. Помогите кто чем может. Сдавать в сентябре, а еще конь не валялся.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.08.2013, 03:40     Лексикографическая сортировка
Посмотрите здесь:

C++ Сортировка подсчетом и LSD сортировка
Сортировка C++
C++ Сортировка
шейкерная сортировка + сортировка слиянием C++
Пирамидальная сортировка и сортировка Шелла C++
2 сортировки: пирамидальная сортировка и сортировка слиянием C++
Сортировка методом "быстрая сортировка" C++
C++ Сортировка Хоара / Быстрая сортировка
C++ Сортировка расчёской и быстрая сортировка
C++ Сортировка Шелла и пирамидальная сортировка для символов
C++ Лексикографическая сортировка по имени
C++ Сортировка Шелла и сортировка вставками

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
12.08.2013, 06:26     Лексикографическая сортировка #2
Цитата Сообщение от Bellfator Посмотреть сообщение
(см. [3,4,9,12])
поясните, что здесь имеется ввиду.

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 10:58     Лексикографическая сортировка #3
Bellfator, в условии описана поразрядная LSD-сортировка. если погуглите, то скорее всего найдете ее реализацию на основе сортировки подсчетом. но если заменить сортировку подсчетом на операции с очередью (как описано в условии), то всё получится.
идея такая: раскладываете слова из основной очереди по вспомогательным очередям в соответствии с текущей буквой, затем сливаете содержимое вспомогательных очередей в основную очередь, затем переходите к следующей букве (левее) и повторяете процесс. еще нужно решить вопрос со словами различной длины.
Bellfator
0 / 0 / 0
Регистрация: 15.04.2013
Сообщений: 17
12.08.2013, 21:35  [ТС]     Лексикографическая сортировка #4
Цитата Сообщение от salam Посмотреть сообщение
поясните, что здесь имеется ввиду.

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.
Задание как раз таки выглядит так, цифры, нам не понятны, но это вроде как Лексикографический порядок, даже препод незнает как сделать
Андрей Xomach
8 / 8 / 0
Регистрация: 22.01.2012
Сообщений: 59
12.08.2013, 21:38     Лексикографическая сортировка #5
Bellfator, http://ru.wikipedia.org/wiki/%D0%9F%...B2%D0%BA%D0%B0
тут есть применение для строк, не оно?
iifat
2184 / 1337 / 98
Регистрация: 05.06.2011
Сообщений: 3,705
13.08.2013, 03:48     Лексикографическая сортировка #6
Не очень какая-то хорошая ссылка. Если и без того знать, оно более-менее понятно, но для первого знакомства лучше, имхо, вот тут почитать.
Yandex
Объявления
13.08.2013, 03:48     Лексикографическая сортировка
Ответ Создать тему
Опции темы

Текущее время: 10:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru