Форум программистов, компьютерный форум CyberForum.ru

Поразрядная сортировка и его недостатки - C++

Войти
Регистрация
Восстановить пароль
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
06.01.2013, 15:58     Поразрядная сортировка и его недостатки #1
Собствено сабж в "плохости" поразрядной сортировки. Ведь, если она отрабатывает за линейное время и не требует спец. аппаратной поддержки, а так же имеет устойчивую реализацию, то почему вместо неё чаще используют либо быструю сортировку Хоара, либо сортировку слиянием? Какие такие у неё недостатки, из-за которых прирост на logN считается малым?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2013, 15:58     Поразрядная сортировка и его недостатки
Посмотрите здесь:

C++ Поразрядная сортировка
C++ Список и его сортировка
C++ Поразрядная сортировка MSD
Трехпутевая поразрядная быстрая сортировка C++
C++ Поразрядная сортировка символьных массивов
Поразрядная сортировка массива C++
Поразрядная операция & C++
C++ Поразрядная конъюнкция / Дизъюнкция / Исключающие, (&), (|), (^)
C++ Поразрядная сортировка
Поразрядная сортировка C++
C++ Поразрядная сортировка
Обменная поразрядная сортировка масива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.01.2013, 17:13     Поразрядная сортировка и его недостатки #2
А как сортировать, например, знаковые числа?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
06.01.2013, 17:54  [ТС]     Поразрядная сортировка и его недостатки #3
Цитата Сообщение от taras atavin Посмотреть сообщение
А как сортировать, например, знаковые числа?
А разве нельзя сортануть отдельно отрицательные (без знака и по убыванию/возрастанию) и положительные (по возрастанию/убыванию)? Вроде как накладок больших не будет
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.01.2013, 18:18     Поразрядная сортировка и его недостатки #4
Два мешающих друг другу алгоритма на одно массиве. Класс! Лучше уж пузырька кубом испортить. А за раз такая пакость. Пусть сортируем по возрастанию, цифры сортируются от младших, значит последним отсортируется старший разряд и так останется. Но у отрицательных он уставновлен, а у положительных сброшен, но при сортировке положительных по возрастанию больше установленный бит, отрицательные уйдут в конец, а они меньше. Оптимальной же будет модификация, учитывающая два бита одновременно, как единое двоичное знаковое число. Алгоритм станет сложным.

Добавлено через 8 минут
И все конкуренты, кроме пузырька, имеют зависимость лучше линейной, а у быстрой сортировки она вообще логаримфмическая, что лучше любой положительной степени. Пузырёк конкурирует только за счёт простоты.
Yandex
Объявления
07.01.2013, 18:18     Поразрядная сортировка и его недостатки
Ответ Создать тему
Опции темы

Текущее время: 13:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru