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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.03.2010, 11:24
John

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

Цифровая сортировка?
Объясните пожалуйста что такое цифровая сортировка на пальцах т.е., её алгоритм (желательно с комментариями) . Заранее спасибо!
  #2  
Старый 03.03.2010, 14:19
MBo MBo вне форума
Местный

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

два варианта - по старшему разряду (MSD) и по младшему (LSD)
По старшему - проще понять.
пусть элементы состоят из K разрядов - например, числа в десятичном виде из двух цифр
25
74
63
22
61
71
13
Делается K проходов (в данном случае 2)
На первом проходе сортируем числа по первой цифре, распределяя их на подгруппы
13

25
22

63
61

74
71
На втором сортируется каждая подгруппа с одинаковым началом по второй цифре
13
22
25
61
63
71
74
Если разрядов больше - продолжаем сортировать подгруппы.
Недостаток - надо как-то организовывать хранение информации о подгруппах с одинаковым началом

При LSD-сортировке сначала происходит сортировка по младшему разряду. Затем по второму с конца и т.д. В данном случае важно, чтобы промежуточная сортировка была устойчивой, т.е. не меняла порядок элементов, для которых уже задан частичный порядок.
25 74 63 22 61 71 13
61 71 22 63 13 74 25 - здесь пары 61 и 63, 22 и 25, 71 и 74 уже упорядочены
13 22 25 61 63 71 74
  #3  
Старый 03.03.2010, 15:15
гость

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

Ответ хороший, только одно не совсем понятно.
MBo, Ваша работа на форуме оплачивается, если не секрет? Из каких фондов?
  #4  
Старый 07.03.2010, 20:03
Новичок

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

Огромное спасибо за ответ. Теперь я всё понял!!!
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Цифровая подпись The_David Реализация, исходники, языки 3 19.04.2008 11:03