Блуждающая сортировка
Stooge sort (Сортировка по частям, Блуждающая сортировка) — рекурсивный алгоритм сортировки с временной сложностью O(n^{2.71}).
Алгоритм
Aлгоритм сортировки списка элементов заключается в следующем:
- Если значение элемента в конце списка больше, чем значение элемента в начале, то поменять их местами.
- Если есть 3 или более элементов в текущем подмножестве списка, то:
- Рекурсивно вызвать Stooge sort для первых 2/3 списка
- Рекурсивно вызвать Stooge sort для последних 2/3 списка
- Рекурсивно вызвать Stooge sort для первых 2/3 списка снова
- Иначе: return
Вывод по блуждающей сортировке
Время работы алгоритма, таким образом, крайне медленное по сравнению с эффективными алгоритмами сортировки, такими, как Сортировка слиянием.