Сдавала сегодня зачет по структурам и алгоритмам обработки данных... И зашел разговор об эффективности (точнее, о скорости работы) разных сортировок.
Почти во всех учебниках написано, что оценка любой сортировки попадает в О(n)-О(n^2)
Я на википедии нашла упоминание о двух непрактичных сортировках:
Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай.
Глупая сортировка (Stupid sort) — O(n^3)
Поиск подробностей в гугле привел к получению горы мусора, к делу не относящейся...
Кто-нибудь что-нибудь знает об этих (а может, еще каких-то) медленных сортировках? Откуда они взялись? Может, они выигрывают по какому-нибудь другому критерию?
То есть зачем люди ищут способ ускорить сортировку (даже с усложнением алгоритма) - понятно, а зачем замедлять с усложнением?
При желании же можно просто рэндомом перемешивать числа, пока они не упорядочатся...
неэффективные сортировки, О(больше n^2) |