tgoop.com/the_algorithms/4563
Last Update:
Блинная сортировка
Алгоритм сортировки, который сортирует неупорядоченную «стопку блинов». В этом алгоритме выполняется операция переворачивания участка стека.
Алгоритм:
Шаг 1. Найдите самый большой блин.
Шаг 2. Переверните стопку, чтобы переместить самый большой «блин» на вершину стека.
Шаг 3. Повторите шаги 2 и 3, но теперь учитывая оставшуюся неотсортированную часть стопки.
Продолжайте пока вся стопка не будет отсортирована: «самый большой блин окажется внизу, а самый маленький — наверху».
Сложность алгоритма:
Лучший случай: O(n) — если массив уже отсортирован, алгоритм может завершиться быстрее, так как будет выполнять меньше переворотов.
Средний случай: O(n²) — алгоритм требует порядка n итераций для нахождения максимального элемента в неотсортированной части массива, и для каждой итерации может потребоваться до n переворотов.
Худший случай: O(n²) — когда элементы находятся в обратном порядке, алгоритму потребуется максимальное количество переворотов для сортировки.
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4563