Придурковатая сортировка :: Stooge sort

Three Stooges
Неэффективная сортировка, представляющая чисто академический интерес.

Метод назван в честь американской комик-группы «Three stooges» («Три придурка»), развлекавшая публику в 30-х-60-х годах прошлого века. Коллектив трио периодически менялся, всего в труппе было 6 актёров за 40 лет существования. В алгоритм заложен элемент абсурда — обычно массив давно отсортирован, но сортировка продолжает безумно метаться по третям списка.

Придурковатая сортировка

Алгоритм

Сравниваем элементы на концах отрезка (первоначально это весь массив). Если на левом конце больше чем на правом, то меняем местами.
Рекурсивно применяем сортировку для первых 2/3 элементов списка.
Рекурсивно применяем сортировку для последних 2/3 элементов списка.
Снова рекурсивно применяем сортировку для первых 2/3 элементов списка.

Характеристики алгоритма

Название Придурковатая сортировка (Stooge sort)
Другие названия Блуждающая сортировка; Сортировка по частям
Класс Сортировки обменами
Устойчивость Устойчивая
Сравнения Да
Сложность по времени Худшая O(nlog 3 / log 1.5)
Средняя
Лучшая
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: Непрактичные сортировки – бессмысленные и беспощадные

Придурковатая сортировка в Википедии
Stooge sort on Wikipedia
Three stooges on Wikipedia
Реализация на различных ЯП

Добавить комментарий