Придурковатая сортировка :: Stooge sort
Неэффективная сортировка, представляющая чисто академический интерес.Метод назван в честь американской комик-группы "Three stooges" ("Три придурка"), развлекавшая публику в 30-х-60-х годах прошлого века. Коллектив трио периодически менялся, всего в труппе было 6 актёров за 40 лет существования. В алгоритм заложен элемент абсурда - обычно массив давно отсортирован, но сортировка продолжает безумно метаться по третям списка.
Алгоритм
- Сравниваем элементы на концах отрезка (первоначально это весь массив).
- Если на левом конце больше чем на правом, то меняем местами.
- Рекурсивно применяем сортировку для первых 2/3 элементов списка.
- Рекурсивно применяем сортировку для последних 2/3 элементов списка.
- Снова рекурсивно применяем сортировку для первых 2/3 элементов списка.
Характеристики алгоритма
| Название | Придурковатая сортировка (Stooge sort) | |
|---|---|---|
| Другие названия | Блуждающая сортировка; Сортировка по частям | |
| Класс | Сортировки обменами | |
| Устойчивость | Устойчивая | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(nlog 3 / log 1.5) |
| Средняя | ||
| Лучшая | ||
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Придурковатая сортировка
Реализация на различных ЯП