Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Алгоритмы _ неэффективные сортировки
Автор: мисс_граффити 21.12.2006 5:37
Сдавала сегодня зачет по структурам и алгоритмам обработки данных... И зашел разговор об эффективности (точнее, о скорости работы) разных сортировок.
Почти во всех учебниках написано, что оценка любой сортировки попадает в О(n)-О(n^2)
Я на википедии нашла упоминание о двух непрактичных сортировках:
Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай.
Глупая сортировка (Stupid sort) — O(n^3)
Поиск подробностей в гугле привел к получению горы мусора, к делу не относящейся...
Кто-нибудь что-нибудь знает об этих (а может, еще каких-то) медленных сортировках? Откуда они взялись? Может, они выигрывают по какому-нибудь другому критерию?
То есть зачем люди ищут способ ускорить сортировку (даже с усложнением алгоритма) - понятно, а зачем замедлять с усложнением?
При желании же можно просто рэндомом перемешивать числа, пока они не упорядочатся...
Автор: volvo 21.12.2006 16:37
Очень хорошее определение BogoSort:
Так что, Кстати, вот еще немного информации:
http://home.tiac.net/~cri_d/cri/2001/badsort.html
Автор: мисс_граффити 21.12.2006 17:26
спасибо!