Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 10.01.2011, 21:18
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

сортировка деревом выбора
Ребят, есть у кого нибудь псевдокод алгоритма сортировки деревом выбора или реализация на С++, буду очень благодарен...
  #2  
Старый 10.01.2011, 21:49
гocть

 
Сообщений: n/a

heap sort что ли?
  #3  
Старый 10.01.2011, 22:11
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

Сообщение от гocть Посмотреть сообщение
heap sort что ли?
нет, heap это пирамидальная...
а вот деревом выбора это другое, там вроде нужно сначала как то в массиве "дерево" сформировать, а потом сортировать сортировкой выбором, вроде так, но могу ошибаться...
  #4  
Старый 10.01.2011, 22:19
гocть

 
Сообщений: n/a

heap - это и есть дерево.
  #5  
Старый 06.04.2011, 09:34
queit

 
Сообщений: n/a

тоже заинтересовался этим видом сортировки, но с реализацией и псевдокодом проблематично. Начал сам пытаться реализовать:
получается, что есть входной массив размерностью N, итоговое дерево будет размером 2*N-1. Нижний уровень нам тоже известен. это есть ничто иное как входной массив.
осталось выстроить n-1 элемент.
дальше, как мне кажется, нужно идти по уровням, которых у нас N/2, а затем по элементам уровня, сравнивая пары. вот здесь у меня и затык полный. как должна сработать рекурсия и как из неё выходить, я не понимаю :-(
  #6  
Старый 06.04.2011, 20:13
гocть

 
Сообщений: n/a

Сообщение от queit Посмотреть сообщение
тоже заинтересовался этим видом сортировки
каким таким этим?
  #7  
Старый 07.04.2011, 06:02
queit

 
Сообщений: n/a

Сообщение от гocть Посмотреть сообщение
каким таким этим?
в самом первом посте смотри внимательно, написано "алгоритма сортировки деревом выбора".
  #8  
Старый 07.04.2011, 09:00
гocть

 
Сообщений: n/a

Сообщение от queit Посмотреть сообщение
в самом первом посте смотри внимательно, написано "алгоритма сортировки деревом выбора".
алгоритм этим четко не определяется

что за дерево выбора? дерево поиска может? heap sort это тоже сортировка деревом. куча - дерево. и она позволяет выбирать максимум...

так что осторожнее в формулировках
  #9  
Старый 07.04.2011, 13:42
queit

 
Сообщений: n/a

(8) открой Вирт Н. "Алгоритмы и структуры данных" страница 108, там описана сортировка с помощью дерева, а дальше про пирамидальную.

"так что осторожнее в формулировках" - именно формулировка вполне корректна :-) смешно, конечно, но так оно и есть :-)
и алгоритм четко определенного вида.

"что за дерево выбора? дерево поиска может? heap sort это тоже сортировка деревом. куча - дерево. и она позволяет выбирать максимум..." - В общем и целом, так - деревья бывают разные (по формулировке и применению), в этом случае используется именно дерево выбора (дерево выбора <> двоичное дерево).

И дело в том что сортировка описана, а реализации нет (изрыл весь инет, хотя может и есть...). Я ею заинтересовался, сейчас на этапе построения этого самого дерева - осталось только с индексами разобраться (пишу на с++). Потом буду реализовывать непосредственно сортировку.

Как сделаю сразе же вынесу на суд общественности ;-)
  #10  
Старый 07.04.2011, 14:43
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Вот что Вирт животворящий пишет:
Изображения:
Тип файла: jpg virt.jpg (50.9 Кб, 137 просмотров)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм наилучшего взаимного выбора Detech Математические алгоритмы (другое) 6 17.11.2010 04:52
Вопрос по правильности выбора обучения Serg555 Искусственный интеллект, нейронные сети 1 16.03.2010 20:03
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Алгоритм, который определяет, является ли граф деревом trans-tech Сортировка и поиск 1 26.11.2008 15:55
Метод квадратичного выбора ToR Сортировка и поиск 12 05.11.2008 23:02