10.01.2011, 20:18
|
|
Новичок
|
|
Регистрация: 05.01.2011
Сообщений: 22
|
|
|
сортировка деревом выбора
Ребят, есть у кого нибудь псевдокод алгоритма сортировки деревом выбора или реализация на С++, буду очень благодарен...
|
|
10.01.2011, 20:49
|
|
|
|
heap sort что ли?
|
|
10.01.2011, 21:11
|
|
Новичок
|
|
Регистрация: 05.01.2011
Сообщений: 22
|
|
Сообщение от гocть
|
|
heap sort что ли?
|
нет, heap это пирамидальная...
а вот деревом выбора это другое, там вроде нужно сначала как то в массиве "дерево" сформировать, а потом сортировать сортировкой выбором, вроде так, но могу ошибаться... |
|
10.01.2011, 21:19
|
|
|
|
heap - это и есть дерево.
|
|
06.04.2011, 08:34
|
|
|
|
тоже заинтересовался этим видом сортировки, но с реализацией и псевдокодом проблематично. Начал сам пытаться реализовать:
получается, что есть входной массив размерностью N, итоговое дерево будет размером 2*N-1. Нижний уровень нам тоже известен. это есть ничто иное как входной массив.
осталось выстроить n-1 элемент.
дальше, как мне кажется, нужно идти по уровням, которых у нас N/2, а затем по элементам уровня, сравнивая пары. вот здесь у меня и затык полный. как должна сработать рекурсия и как из неё выходить, я не понимаю :-(
|
|
06.04.2011, 19:13
|
|
|
|
Сообщение от queit
|
|
тоже заинтересовался этим видом сортировки
|
каким таким этим? |
|
07.04.2011, 05:02
|
|
|
|
Сообщение от гocть
|
|
каким таким этим?
|
в самом первом посте смотри внимательно, написано "алгоритма сортировки деревом выбора". |
|
07.04.2011, 08:00
|
|
|
|
Сообщение от queit
|
|
в самом первом посте смотри внимательно, написано "алгоритма сортировки деревом выбора".
|
алгоритм этим четко не определяется
что за дерево выбора? дерево поиска может? heap sort это тоже сортировка деревом. куча - дерево. и она позволяет выбирать максимум...
так что осторожнее в формулировках |
|
07.04.2011, 12:42
|
|
|
|
(8) открой Вирт Н. "Алгоритмы и структуры данных" страница 108, там описана сортировка с помощью дерева, а дальше про пирамидальную.
"так что осторожнее в формулировках" - именно формулировка вполне корректна :-) смешно, конечно, но так оно и есть :-)
и алгоритм четко определенного вида.
"что за дерево выбора? дерево поиска может? heap sort это тоже сортировка деревом. куча - дерево. и она позволяет выбирать максимум..." - В общем и целом, так - деревья бывают разные (по формулировке и применению), в этом случае используется именно дерево выбора (дерево выбора <> двоичное дерево).
И дело в том что сортировка описана, а реализации нет (изрыл весь инет, хотя может и есть...). Я ею заинтересовался, сейчас на этапе построения этого самого дерева - осталось только с индексами разобраться (пишу на с++). Потом буду реализовывать непосредственно сортировку.
Как сделаю сразе же вынесу на суд общественности ;-)
|
|
07.04.2011, 13:43
|
|
Местный
|
|
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,368
|
|
|
Вот что Вирт животворящий пишет:
|
|
| Опции темы |
Поиск в этой теме |
|
|
|
| Опции просмотра |
 Линейный вид
|
|
| |
