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

С++ для начинающих

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

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

12.08.2013, 03:40. Просмотров 2517. Ответов 5
Метки нет (Все метки)

Задача:

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

Указания:

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

________________________________________________________________________________________________________




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

Лексикографическая сортировка по имени - C++
Привет всем форумчанам! Вот у меня такая проблемка: нужно реализовать лексикографическую сортировку по имени, а для этого придумать...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

5
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 732
12.08.2013, 06:26 #2
Цитата Сообщение от Bellfator Посмотреть сообщение
(см. [3,4,9,12])
поясните, что здесь имеется ввиду.

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

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.
Задание как раз таки выглядит так, цифры, нам не понятны, но это вроде как Лексикографический порядок, даже препод незнает как сделать
0
Андрей 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
тут есть применение для строк, не оно?
0
iifat
2249 / 1405 / 105
Регистрация: 05.06.2011
Сообщений: 3,863
13.08.2013, 03:48 #6
Не очень какая-то хорошая ссылка. Если и без того знать, оно более-менее понятно, но для первого знакомства лучше, имхо, вот тут почитать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2013, 03:48
Привет! Вот еще темы с ответами:

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Сортировка вектора по полю(Сортировка вставками) - C++
Здравствуйте! Нужно написать сортировку вектора по полю weight класса tomato. Вот класс: #pragma once #include &lt;iostream&gt; ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....


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

Или воспользуйтесь поиском по форуму:
6
Yandex
Объявления
13.08.2013, 03:48
Ответ Создать тему
Опции темы

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