Глупая сортировка :: Stupid sort

Простейший учебный алгоритм низкой эффективности. При минимальном изменении трансформируется в пузырьковую сортировку или гномью сортировку.

Глупая сортировка

Алгоритм

Просматриваем массив начиная с первого индекса, по пути сравниваем соседние элементы. Если находим неотсортированную пару — меняем местами, возвращаемся в начало массива и повторяем те же действия.

Процесс заканчивается, если во время полного прохода не обнаружено ни одной неотсортированной пары.

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

Название Глупая сортировка (Stupid sort)
Класс Сортировки обменами
Устойчивость Устойчивая
Сравнения Да
Сложность по времени Худшая O(n3)
Средняя O(n3)
Лучшая O(n3)
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: Глупая сортировка и некоторые другие, поумнее
Хабрахабр: Пузырьковая сортировка и все-все-все

Глупая сортировка в Википедии

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