Рассмотрю сортировку массива пузырьком по возрастанию. В этом случае суть алгоритма сводится к обмену рядом стоящих элементов, если элемент слева больше, чем справа. Попарно проверяем все элементы, двигаясь по массиву направо (это справедливо именно для сортировки по возрастанию)...

Идея оптимизации Посредством добавления флага swapped, который будет равняться true, если на предыдущей итерации элементы были поменяны местами хотя бы один раз, иначе будет равняться false. Теперь, если мы увидим, что swapped == false, то есть на предыдущей итерации мы не встретили хотя бы два элемента, идущие не по порядку (то есть все элементы стоят по порядку, а следовательно...