Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 41
> Ничего не мешает сортировать и дробные числа, если перед тем привести их к целым (например, всё умножить на 10k, отсортировать, а потом разделить на 10k).
Ничего, кроме необходимости выделить 10k памяти.
Ничего, кроме необходимости выделить 10k памяти.
Вовсе нет, если речь о Double, то ничего не изменится. Проблемой тут будет только вылет возможных сортируемых значений за предел double при умножении.
Хабр, ты окончательно ебанулся.
Под эту сортировку выделяется N * Max памяти, где N — число элементов, max — максимальная величина элемента. В любую реализацию гляньте, блин.
На сортировку N целых чисел, таким образом, нужно N * Max * sizeof(int) памяти.
На сортировку дробных чисел нужно будет N * round(Max * 10k) * sizeof(int) памяти, потому что умножение на 10k увеличивает максимальное значение. Это верно вообще для всех сортировок вычёрпыванием.
Технический ресурс, my ass.
Под эту сортировку выделяется N * Max памяти, где N — число элементов, max — максимальная величина элемента. В любую реализацию гляньте, блин.
for (i = 1, max = a[0]; i < len; i++)
if (a[i] > max) max = a[i];
beads = calloc(1, max * len);
На сортировку N целых чисел, таким образом, нужно N * Max * sizeof(int) памяти.
На сортировку дробных чисел нужно будет N * round(Max * 10k) * sizeof(int) памяти, потому что умножение на 10k увеличивает максимальное значение. Это верно вообще для всех сортировок вычёрпыванием.
Технический ресурс, my ass.
Не надо так переживать. Неэффективные алгоритмы тоже полезны для рассмотрения, как в методологических, так и педагогических целях.
Причем здесь неэффективные алгоритмы? Я переживаю за пять минусов у технически корректного комментария.
Рискну предположить что минусы не за техническую корректность :)
Прям затрудняюсь понять, чьи нежные чувства я задел фразой «Ничего, кроме необходимости выделить 10k памяти.»
Ах, да, я имел в виду вашу реплику чуть ниже. Точно, там ведь (на текущий момент) 6 минусов, а не 5 :)
Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.
Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.
> Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.
Ах да, точно! )
Мы же их на единицы раскладываем. Тогда понадобится. )
Мы же их на единицы раскладываем. Тогда понадобится. )
Это всё от того, что на анимации в посте показан вырожденный случай — ряд сортируемых элементов содержит все элементы, от первого до последнего, без пустых мест. Если бы показывали сортировку ряда «0-2-4-6-8-10», то стало бы очевидно — для такой сортировки потребуется таблица 6 столбцов * 11 строк.
Ну и некоторые, типа меня, не проснулись к моменту чтения поста.
>>Ничего, кроме необходимости выделить 10k памяти.
Вы хотели сказать «10k памяти на каждую строку» — разница довольно существенна.
Ну и некоторые, типа меня, не проснулись к моменту чтения поста.
>>Ничего, кроме необходимости выделить 10k памяти.
Вы хотели сказать «10k памяти на каждую строку» — разница довольно существенна.
Аааа, жуткая сортировка. А если надо сортировать 64битные числа, где же столько памяти взять?
С выделяемой памятью конечно перегиб — недопустимые в реальных проектах объемы. Но сортировка интересна и проста. Спасибо топикстартеру за интересный и хорошо оформленный пост.
Какое-то странное описание алгоритма. Если выкинуть из него физические шарики — то получится всем известная сортировка подсчетом, с временем работы O(n+m) и такой же требуемой памятью. Здесь n — количество сортируемых чисел, а m — количество возможных значений сортируемых чисел.
O(n2) — это худший случай по памяти. Максимальное количество возможных значений n сортируемых натуральных чисел как раз равно n. В худшем случае m = n.
Почему при оценке памяти именно умножение, а не сложение? Потому что изначально входной массив из n элементов, а дополнительно приходится обрабатывать матрицу n x n (в худшем случае).
Насчёт counting sort. Да, бисерная сортировка — это сортировка подсчётом, но только через «одно место», ухудшенный вариант. Вместо того чтобы обрабатывать сами сортируемые числа, мы обрабатываем каждую единичку каждого числа. Всего единиц в массиве натуральных чисел равно сумме всех чисел S, отсюда и временная сложность O(S).
Сортировать бусинками невыгодно с какой стороны ни посмотри, но для пятничного поста алгоритм вполне годится :)
Почему при оценке памяти именно умножение, а не сложение? Потому что изначально входной массив из n элементов, а дополнительно приходится обрабатывать матрицу n x n (в худшем случае).
Насчёт counting sort. Да, бисерная сортировка — это сортировка подсчётом, но только через «одно место», ухудшенный вариант. Вместо того чтобы обрабатывать сами сортируемые числа, мы обрабатываем каждую единичку каждого числа. Всего единиц в массиве натуральных чисел равно сумме всех чисел S, отсюда и временная сложность O(S).
Сортировать бусинками невыгодно с какой стороны ни посмотри, но для пятничного поста алгоритм вполне годится :)
Если я правильно понял, то самое интересное в том, что сложность может быть меньше, чем O(n log(n)); а это минимум для сортировки сравнением.
O(n log n) — это минимум для сортировок абстрактных элементов с определенной на них функцией сравнения. Т.е. алгоритм ничего не знает ни о природе элементов, ни об их начальном расположении.
Здесь же сортируются исключительно натуральные числа и алгоритм использует их свойства. Еще пример — поразрядная сортировку с временем O(nk).
Здесь же сортируются исключительно натуральные числа и алгоритм использует их свойства. Еще пример — поразрядная сортировку с временем O(nk).
Да, самое интересное в семействе сортировок подсчетом — тот факт, что сложность может быть меньше Ω(n log n)
Я бы сменил хаб «Совершенный код» на «Ненормальное программирование» :)
А кст, хоть и узко-специализированная, зато в редких случаях может быть крайне полезной. В копилку.
З.Ы. ссылочка на реализацию утянула на 30 минут рассматривания синтаксисов :)
З.Ы. ссылочка на реализацию утянула на 30 минут рассматривания синтаксисов :)
При чём тут Абак? Ладно, представим, что у нас есть «физический процессор» с падающими шарами и оттуда получается такая сложность O(n**0.5), но что за сложность O(1)? И можно ли любому алгоритму придать такую сложность с приписом «всё одновременно сдвигается и считается»?
Чаще всего сортировку наглядно представляют как бисер нанизанный на спицы. Или как шарики, скатывающиеся по узким желобкам. Второй вариант мне был проще для создания анимации.
O(1) — это результат некоего теоретизированного рассуждения, мысленный эксперимент с участием идеального физического устройства в идеальных условиях, реализующего эту сортировку. Если абсолютно исключить трение, поместить устройство вблизи сверхмассивного тела, мгновенно и одномоментно предоставить шарикам возможность упасть вниз по спицам — то временная сложность будет стремиться как раз к такому значению. Как-то так.
O(1) — это результат некоего теоретизированного рассуждения, мысленный эксперимент с участием идеального физического устройства в идеальных условиях, реализующего эту сортировку. Если абсолютно исключить трение, поместить устройство вблизи сверхмассивного тела, мгновенно и одномоментно предоставить шарикам возможность упасть вниз по спицам — то временная сложность будет стремиться как раз к такому значению. Как-то так.
Вы забыли, что шарики следует сначала разместить (по-одному), а потом еще и подсчитать обратно.
Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти. Простите за корявую формулировку, но более точные формулировки хуже передают суть.
Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти. Простите за корявую формулировку, но более точные формулировки хуже передают суть.
>>> Вы забыли, что шарики следует сначала разместить (по-одному), а потом еще и подсчитать обратно.
Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия. Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.
>>> Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти.
Бисерная сортировка примечательна тем, что её часто рассматривают не как алгоритм/программу, а как некое физическое устройство с шариками на спицах или электрическую цепь из резисторов. Речь о памяти в этом случае просто не идёт.
Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия. Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.
>>> Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти.
Бисерная сортировка примечательна тем, что её часто рассматривают не как алгоритм/программу, а как некое физическое устройство с шариками на спицах или электрическую цепь из резисторов. Речь о памяти в этом случае просто не идёт.
а реализация на квантовом компьютере не будет иметь О(1)? чисто теоретически?
Надо будет на досуге отписаться авторам сортировки и спросить у них. В конце концов, они все специалисты по квантовым вычислениям.
Алгоритм абсолютно безумный, но на реализации на RosettaCode поглядеть забавно. Как элегантно выглядит реализация на Хаскеле:
import Data.List
beadSort :: [Int] -> [Int]
beadSort = map sum. transpose. transpose. map (flip replicate 1)
Не понятно, как в такой сортировке данные к ключу привязывать? Т.е. например отсортировать строки в таблице по натуральному ключу?
А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
>>> Не понятно, как в такой сортировке данные к ключу привязывать?
В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
>>> Т.е. например отсортировать строки в таблице по натуральному ключу?
Алгоритм использует свойства натуральных чисел и поэтому «заточен» прежде всего под упорядочивание целых чисел больше нуля.
Сортировать бисером можно и что-то другое, строки в том числе (можно придумать какие-то способы приведения строку в целое число и обратно), но это уже извращение. Сортировка изначально придумана под натуральные числа.
>>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
Сортировка подсчётом во всех отношениях намного эффективнее чем бисерная сортировка. Более того — бисерная сортировка это разновидность сортировки подсчётом, причём разновидность весьма медленная и крайне расточительно использующая память.
Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.
В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
>>> Т.е. например отсортировать строки в таблице по натуральному ключу?
Алгоритм использует свойства натуральных чисел и поэтому «заточен» прежде всего под упорядочивание целых чисел больше нуля.
Сортировать бисером можно и что-то другое, строки в том числе (можно придумать какие-то способы приведения строку в целое число и обратно), но это уже извращение. Сортировка изначально придумана под натуральные числа.
>>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
Сортировка подсчётом во всех отношениях намного эффективнее чем бисерная сортировка. Более того — бисерная сортировка это разновидность сортировки подсчётом, причём разновидность весьма медленная и крайне расточительно использующая память.
Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.
Вот, кстати, подумал, что не знаю, как назвать класс сортировок, которые основаны на обмене элементов. Т.е. в отличии от бисерной или подсчетом сохраняют возможность связи с данными.
Т.е., например, при быстрой сортировке я могу вместе с ключом хранить ссылку на какой-то элемент, и при упорядочивании по ключу, потом могу упорядочить сами элементы.
А при сортировки подсчетом, такую связь невозможно установить в принципе, т.к. упорядоченный ключ генерируется, а не получается в результате изменения существующего списка.
При этом, если у сортировок первого класса — широкий диапазон применения, то у второго класса — довольно узок. Не знаете ли правильного термина, для того, чтобы отделить первый класс от второго. Нагуглить не удалось.
Т.е., например, при быстрой сортировке я могу вместе с ключом хранить ссылку на какой-то элемент, и при упорядочивании по ключу, потом могу упорядочить сами элементы.
А при сортировки подсчетом, такую связь невозможно установить в принципе, т.к. упорядоченный ключ генерируется, а не получается в результате изменения существующего списка.
При этом, если у сортировок первого класса — широкий диапазон применения, то у второго класса — довольно узок. Не знаете ли правильного термина, для того, чтобы отделить первый класс от второго. Нагуглить не удалось.
Сортировки бывают таких видов:
Сортировки обменами
Сортировки вставками
Сортировки выбором
Сортировки слиянием
Сортировки распределением
Гибридные сортировки
Параллельные сортировки
Быстрая относится к обменным.
Распределительные сортировки (подсчётом, поразрядная, блочная) не используют сравнения элементов массива между собой и ключи поэтому не сохраняются. Эти сортировки классифицируют элементы по общим признакам.
Они обычно работают быстрее чем известные эффективные сортировки других видов (quick sort, merge sort, heap sort и кое-какие другие) но Вы точно заметили их существенный недостаток: ограниченная применимость (обычно заточены под целые числа или строки).
Быстрая сортировка работает очень быстро и она универсальна. Поэтому она так популярна и широко используема. Но для каких-то узких специфических задач другие сортировки могут работать намного быстрее.
Сортировки обменами
Сортировки вставками
Сортировки выбором
Сортировки слиянием
Сортировки распределением
Гибридные сортировки
Параллельные сортировки
Быстрая относится к обменным.
Распределительные сортировки (подсчётом, поразрядная, блочная) не используют сравнения элементов массива между собой и ключи поэтому не сохраняются. Эти сортировки классифицируют элементы по общим признакам.
Они обычно работают быстрее чем известные эффективные сортировки других видов (quick sort, merge sort, heap sort и кое-какие другие) но Вы точно заметили их существенный недостаток: ограниченная применимость (обычно заточены под целые числа или строки).
Быстрая сортировка работает очень быстро и она универсальна. Поэтому она так популярна и широко используема. Но для каких-то узких специфических задач другие сортировки могут работать намного быстрее.
Сортировка подсчетом сохраняет возможность связи с данными. Более того, она при этом еще и является устойчивой.
Кстати, на данном свойстве сортировки подсчетом основывается поразрядная сортировка.
Кстати, на данном свойстве сортировки подсчетом основывается поразрядная сортировка.
Ах да. Еще небольшое замечание.
На вопрос:
>> Не понятно, как в такой сортировке данные к ключу привязывать?
Вот такой ответ:
>В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
подразумевает, что в этих реализациях раскрывается способ, как привязать.
Однако это не так. Видимо, правильный ответ: ни как. Как и в сортировке подсчетом.
На вопрос:
>> Не понятно, как в такой сортировке данные к ключу привязывать?
Вот такой ответ:
>В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
подразумевает, что в этих реализациях раскрывается способ, как привязать.
Однако это не так. Видимо, правильный ответ: ни как. Как и в сортировке подсчетом.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Бисерная сортировка (Bead sort)