403
правки
Изменения
м
→Сложность
== Сложность ==
В данной сортировке выполняются всего две два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим обмен всех все необходимые обмены элементов.
Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Несложно посчитать, что количество инверсий в таком массиве <tex dpi="150"> \frac {n \cdot (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.
