Идея оптимизации Посредством добавления флага swapped, который будет равняться true, если на предыдущей итерации элементы были поменяны местами хотя бы один раз, иначе будет равняться false. Теперь, если мы увидим, что swapped == false, то есть на предыдущей итерации мы не встретили хотя бы два элемента, идущие не по порядку (то есть все элементы стоят по порядку, а следовательно массив отсортирован), то мы можем заранее закончить сортировку массива, гарантируя, что он отсортирован. В то время, как стандартный алгоритм Bubble Sort, продолжал бы производить ненужные итерации, сортируя уже отсортированный массив, пока не перебрал бы все его элементы. Время работы | Сложность В худшем случае - O(N^2) Реализация Код на c++ Код на c:
Идея оптимизации
Посредством добавления флага swapped, который будет равняться true, если на предыдущей итерации элементы были поменяны местами хотя бы один раз, иначе будет равняться false.
Теперь, если мы увидим, что swapped == false, то есть на предыдущей итерации мы не встретили хотя бы два элемента, идущие не по порядку (то есть все элементы стоят по порядку, а следовательно массив отсортирован), то мы можем заранее закончить сортировку массива, гарантируя, что он отсортирован. В то время, как стандартный алгоритм Bubble Sort, продолжал бы производить ненужные итерации, сортируя уже отсортированный массив, пока не перебрал бы все его элементы.
Время работы | Сложность
В худшем случае - O(N^2)
Реализация
Код на c++
Код на c: