пузырьковая сортировка. так надо. Пузырьковая сортировка
 Скачать 1.06 Mb.
|
Доклад на тему: «Пузырьковая сортировка»Подготовил студентИнформация о сортировкеПузырьковая сортировка, иногда называемая тонущей сортировкой, - это простой алгоритм сортировки, который многократно просматривает список, сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке. Проход по списку повторяется до тех пор, пока список не будет отсортирован. Еще немного информации о нейСортировка “Пузырьком” называется так, потому что самый большой “пузырь” всегда всплывает вверх, за ним следует пузырь поменьше и так далее до самого маленького “пузырька”. Данная сортировка является одним из самых простейших видов сортировок. Именно на ее основе придумали такие виды, как: шейкерную и четно-нечетную сортировки. Асимптотика в худшем и среднем случае – O(n2), в лучшем случае – O(n). Принцип работыКак работает алгоритм пузырьковой сортировки Принцип работы пузырьковой сортировки можно описать в три пункта:
Ниже вы можете увидеть, как работает пузырьковая сортировка в действии. Сложность алгоритмаПредположим, у необходимо отсортировать массив из 10 элементов. Внешний цикл сделает 9 операций, внутренний каждый раз на интеграцию меньше т.е. 9, 8, 7, 6, … , 1. Всего будет произведено 9+8+7+6+5+4+3+2+1 = 45 шагов в случае если массив был отсортирован в обратную сторону. Получаем, что сложность примерно N^2/2, где N – количество элементов массива. В обозначении О – синтаксиса сложность равна О(N^2). Основной минус алгоритма сортировки “Пузырьком” – его медленная скорость. Блок-схемаПример программы на С++Список информационных источников
Спасибо за внимание ! |