0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
1 | |
Quicksort для bidirectional_iterator либо (в крайнем случае) для списка25.09.2017, 01:16. Показов 882. Ответов 12
Метки нет (Все метки)
Здравствуйте, можно ли реализовать такую сортировку? Очень нужно для лабораторной.
Заранее благодарю за помощь.
0
|
25.09.2017, 01:16 | |
Ответы с готовыми решениями:
12
QuickSort двунаправленного списка для полей типа string Создание выпадающего списка (для выбора из альтернатив) для какой либо сущности на форме edit Матрица с равной суммой чисел. GNU Prolog, в крайнем случае SWI. Устранение ошибки и доведение до работоспособного состояния Найти либо максимум, либо минимум для трех задаваемых чисел |
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
|
25.09.2017, 01:27 | 2 |
для двунаправленного итератора можно запилить обертку, с помощью которой можно будет получить random access итератор. поэтому, если для квиксорта единственное требование - рандом эккесс доступ, то можно. но будет очень очень не эффективно.
0
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
25.09.2017, 01:33 [ТС] | 3 |
0
|
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
|
25.09.2017, 02:30 | 4 |
нет. обертку - это написать полноценный класс итератора со всеми нужными для квиксорта операциями.
арифметические опреаторы или что там используется? операторы доступа по индексу? вот тут можно покопаться: http://www.boost.org/doc/libs/... acade.html но такой итератор уже не будет бидирекшнитератором. поэтому ответ не однозначный. Добавлено через 3 минуты эээ, я вот почитал ваш пост и вот какие вопросы: если у вас задача - написать такой итератор или реализовать самостоятельно алгоритм для таких итераторов - то это одно. если же просто списки сортировать, то: если вы используете std::list, то тут все понятно. использовать метод списка sort. он в виде метода а не в виде обобщенного алгоритма как раз из-за особенностей структуры списка ну и итераторов. если не списком пользуйетесь, то перекладывайте в какой-нибудь std контейнер, сортируйте его, потом обратно.
0
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
25.09.2017, 02:51 [ТС] | 5 |
DU3, Я использую Дек, но написал я его сам (так по заданию). Для него я могу реализовать только Двунаправленный итератор (не так ли?) - обёртку для него я уже написал. Так же по заданию я должен написать несколько сортировок, и одна из них - Быстрая. В задании не сказано, что я должен написать итератор, но в общем оно так построено, что без итераторов мне не обойтись.
То есть по сути такая задача у меня и стоит. Добавлено через 6 минут Небольшое пояснение: в задании я должен реализовать два наследника класса Последовательность, один из них должен работать как массив, другой - как список. Алгоритм сортировки должен позволять сортировать их независимо от того, какой наследник сортируется. Я предполагаю, что нормального способа, кроме как писать итераторы, нет. (можно ещё перегрузку устроить, конечно, но, что если придётся добавить ещё какого-нибудь наследника?..) К тому же нельзя сортировку пихать в сам класс.
0
|
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
|
25.09.2017, 02:55 | 6 |
у стандартного std::deque итератор произвольного доступа. так что вы свой итератор как-то не так сделали и искуствено ограничили его фичи. имея итератор произвольного доступа задача по сортировке будет сильно проще имхо. так что вам стоит пересмотреть его реализацию, он однозначно может быть итератором произвольного доступа причем значительно более эффективного, чем в случае обертки над двунаправленным итератором.
0
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
25.09.2017, 03:03 [ТС] | 7 |
DU3, std::degue - это смесь списка с массивом, но сейчас мне нужен чистый список(что-то типа std::list - а у него Двунаправленный).
Добавлено через 2 минуты Согласен
0
|
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
|
25.09.2017, 03:07 | 8 |
ну вы дек в реализации упомянули, я вам и написал что там все ок с итераторами.
поищите в сети готовые решения чтоли. вот первое что попалось: http://www.geeksforgeeks.org/q... nked-list/ может еще что полезное есть.
1
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
25.09.2017, 03:10 [ТС] | 9 |
Это интересно, может и пойдёт.
Добавлено через 1 минуту Хм.. а разве дек (по-правильному) не Двусвязный список?
0
|
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
||||||
25.09.2017, 03:23 | 10 | |||||
и еще раз: вы сказали что нельзя сортировку пихать в метод класса. это будет ну очень не эффективно. в stl функция сортировки для списка не просто так. если бы можно сделать обобщенный алгоритм эффективным для всех типов итераторов - так бы и сделали. если все-же ваша задача оставить при этом одну обобщенную функцию - то тут или адаптировать двунаправленный итератор с целью работать с ним как с итератором произвольного доступа или очень хитро писать саму эту функцию, но это почти такое же решение, что и первое, но требующее других заморочек.
в общем для своего двунаправленного итератора вы можете запилить арифметические операции вроде:
Добавлено через 1 минуту дэк - это double ended queue (двусторонняя очередь). реализуется как правило в виде кусков массивов. куски эти - узлы списка. в предельном случае, когда размер динамических массивов == 1 получаем двусторонний список. Добавлено через 5 минут *двусвязный список, не двусторонний
0
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
|
25.09.2017, 03:31 [ТС] | 11 |
Да проблема то не в +, и не в -. Проблема в >, < и т.п.
Вот я и пытаюсь эту функцию хитро написать. Почти получилась Быстрая сортировка по алгоритму Ломуто( из wiki), но, боюсь её нельзя назвать полноценной Быстрой сортировкой Добавлено через 3 минуты Задача эффективности, честно говоря не стоит
0
|
284 / 232 / 114
Регистрация: 07.09.2016
Сообщений: 584
|
|
25.09.2017, 03:54 | 12 |
это типа какой итератор стоит перед другим итератором? если так, то если внутри итератора есть ссылка на контейнер и есть возможность получить скажем первый итератор этого контейнера, то такими инкрементальными шагами можно определить, на каком расстоянии от начала находится каждый из итераторов и сравнивать эти расстояния. это расстояние получается что-то вроде индекса в случае обычных массивов.
0
|
0 / 0 / 0
Регистрация: 16.03.2017
Сообщений: 51
|
||||||
25.09.2017, 16:39 [ТС] | 13 | |||||
Идею понял, но звучит ужасно.
Добавлено через 12 часов 37 минут В общем, то чего я смог добиться.
0
|
25.09.2017, 16:39 | |
25.09.2017, 16:39 | |
Помогаю со студенческими работами здесь
13
Составить программу, вычисляющую для двух заданных комплексных чисел z1 и z2 либо величину z1/z2, либо z2/z1 Изменить методы так, чтобы для заданного значения n (в нашем случае для n=5 ) на экран выводилась следующая таблица Изменить методы так, чтобы для заданного значения n (в нашем случае для n=7 ) на экран выводилась следующая таблица Для чисел из файла указать его значение в обратном либо дополнительном коде, либо его инверсию по выбору Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |