Выполняя практическую работу по улучшению алгоритма пузырьковой сортировки, возник вопрос, как вывести аналитическую формулу, которая связывает число итераций оптимизированной пузырьковой сортировки от размера сортируемого массива?

Итак имели что-то вроде (n-1) + (n-2) + (n-3) + 3 + 2 + 1

Но ведь это похоже на 1 + 2 + 3 + …. + (n-1) !!!

А это же старая байка о Гауссе, который решил моментально задачу сложения от 1 до 100, не успел учитель даже дверь класса закрыть.

Согласно легенде, школьный учитель математики, чтобы занять детей на долгое время, предложил им сосчитать сумму чисел от 1 до 100. Юный Гаусс заметил, что попарные суммы с противоположных концов одинаковы: 1 + 100 = 101, 2 + 99 = 101 и т. д. Раз чисел в ряду у нас 100, это значит,что 50 пар числа 101. Затем умножаем 101 на 50 и мгновенно получим результат 101 * 50 = 5050.

То есть n = 100.

Тогда будет 50 = 100/2 = n/2

а 101 это n+1

Значит, формула Гаусса будет (n+1)*n/2

Применительно к первому вопросу о формуле, описывающей число итераций оптимизированной пузырьковой сортировки, то здесь просто надо вместо n+1 вписать n-1

то есть: (n-1)*n/2

А тут можно увидеть визуализацию 8 наиболее популярных алгоритмов сортировки