27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
1 | |
Каковы варианты сортировки связного списка05.09.2014, 00:45. Показов 5314. Ответов 23
Метки нет (Все метки)
Дорого времени суток.
Есть двусвязный список хранящий допустим int, какие есть варианты по его сортировки? Например: 1. Считать все данные со списка в массив, отсортировать массив (можно через указатели), удаляем старый список и записываем новый (сортировать напрямую почему то не вышло((( ); 2. При добавлении данных в список, вставлять > data > ; Подскажите свои/правильный вариант...
0
|
05.09.2014, 00:45 | |
Ответы с готовыми решениями:
23
Не срабатывает функция сортировки связного списка Создание двойного связного списка целых чисел, вводимых с клавиатуры; печать списка Напишите процедуру сортировки линейного связного списка методом простого выбора с изменением указателей Каковы варианты решения?) |
27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
05.09.2014, 00:57 [ТС] | 3 |
0
|
05.09.2014, 01:04 | 4 | |||||||||||||||
Обычная сортировка пузырьком:
Списки не поддерживают быструю операцию индексирования. Ее можно реализовать так, но ее сложность будет O(N), где N - количество элементов в списке:
0
|
27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
05.09.2014, 10:48 [ТС] | 5 |
Либо я что то не понимаю, либо тут мы "двигаем" данные. Если это так, разве это приемлемо?
Добавлено через 9 часов 32 минуты тема все еще актуальна...
0
|
20 / 20 / 3
Регистрация: 25.05.2011
Сообщений: 62
|
|
05.09.2014, 11:24 | 6 |
Если честно, я вообще не понял, при чем тут индексация и приведенный код. Возможно человек просто не все вставил из буфера обмена.
0
|
27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
06.09.2014, 10:00 [ТС] | 8 |
0
|
27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
06.09.2014, 10:11 [ТС] | 10 |
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
06.09.2014, 10:16 | 11 |
Точнее даже не так. Нужны a+j и a+j+1. a - это не только массив, но и указатель на начало этого массива.
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
||||||||||||||||
06.09.2014, 10:30 | 13 | |||||||||||||||
Берём
1
|
27 / 27 / 11
Регистрация: 15.10.2013
Сообщений: 880
|
|
06.09.2014, 10:34 [ТС] | 14 |
0
|
06.09.2014, 10:55 | 15 |
Вообще-то списки часто используются для хранения структур и сортировку приходится делать по полю списка. В этом случае перестановка значений одного поля не подойдет, надо перебрасывать указатели. Для изучения работы с указателями это годится, а для решения реальных задач сортировки лучше использовать STL, например. Там и скорость написания (когда ее освоишь) и скорость работы и универсальность.
Я даже думаю, что если программист может освоить STL, он должен ее освоить А если не может, то ему лучше изучать другой язык, не C++
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
||||||
06.09.2014, 11:31 | 16 | |||||
Можно аналогично перемещать все поля. Кроме того, структура может валять в ->Data.
Добавлено через 30 минут Но если охота съэкономить операции, то:
0
|
Заблокирован
|
||||||
06.09.2014, 11:37 | 17 | |||||
Сообщение было отмечено andreyananas как решение
Решение
andreyananas, лови
Не по теме: ЗЫ Такие задания без реализации списка в заголовке темы никто не любит, т.к минимум нужно писать свою реализацию списка. Учти это на будующее когда будешь просить помогать с подобными задачами.
2
|
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
|
|
06.09.2014, 12:08 | 18 |
Какая жестокая ошибка... Быстрая сортировка (разумеется, без индексирования) как раз отлично подходит для списков. Что может быть проще, чем сделать из одного списка два, а потом срастить их обратно?
1
|
06.09.2014, 16:58 | 19 |
Выбор опорного элемента. Как его выбрать быстро в списке? Брать первый или последний элемент ухудшит ассимптотику. Решается набором костылей, например, поддерживать доп. массив значений и в каждом элементе списка хранить позицию, на которой он находится в этом массиве.
С этим дополнительным массивом выходит, тоже самое, что и сортировка массива. Добавлено через 9 минут Хм. Если выбирать рандомный элемент и проходить к нему по списку, то кол-во операций увеличивается в 1,5 раза. Некритично, признаю свою ошибку Кстати, тут и склеивание списков не понадобится.
0
|
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
|
|
06.09.2014, 19:06 | 20 |
А если попробовать брать среднее арифметическое двух первых элементов, может получиться даже ещё лучше.
0
|
06.09.2014, 19:06 | |
06.09.2014, 19:06 | |
Помогаю со студенческими работами здесь
20
Каковы варианты создания строки навигации по дереву (как, например, в Windows - строка пути) Сортировка связного списка Реализация связного списка Сортировка связного списка Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |