Сдавала сегодня зачет по структурам и алгоритмам обработки данных... И зашел разговор об эффективности (точнее, о скорости работы) разных сортировок.
Почти во всех учебниках написано, что оценка любой сортировки попадает в О(n)-О(n^2)
Я на википедии нашла упоминание о двух непрактичных сортировках:
Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай.
Глупая сортировка (Stupid sort) — O(n^3)
Поиск подробностей в гугле привел к получению горы мусора, к делу не относящейся...
Кто-нибудь что-нибудь знает об этих (а может, еще каких-то) медленных сортировках? Откуда они взялись? Может, они выигрывают по какому-нибудь другому критерию?
То есть зачем люди ищут способ ускорить сортировку (даже с усложнением алгоритма) - понятно, а зачем замедлять с усложнением?
При желании же можно просто рэндомом перемешивать числа, пока они не упорядочатся...
Полная версия: неэффективные сортировки
Очень хорошее определение BogoSort:
Так что,
Кстати, вот еще немного информации:
Inefficient sort algorithms
Цитата(http://catb.org/~esr/jargon/html/B/bogo-sort.html)
Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order.
Так что, Цитата
можно просто рэндомом перемешивать числа, пока они не упорядочатся...
- это оно и есть...Кстати, вот еще немного информации:
Inefficient sort algorithms
спасибо!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.