Проходим массив ключей слева направо, сравнивая соседние ключи.
Если они стоят не по порядку, меняем их местами. Если в процессе просмотра не было обменов
местами, то работа закончена, в противном случае повторяем процесс.
Метод пузырька носит такое название, потому что в результате одного просмотра
таблицы, запись с наибольшим значением ключа перемещается вверх (если считать,
что в верхней части таблицы располагаются наибольшие значения ключей),
то есть всплывает как пузырек воздуха в жидкости.
Время работы алгоритма пропорционально N2.
Анализ алгоритма довольно сложен и здесь не приводится.
Быстродействие можно несколько улучшить, если просматривать
массив не далее места последнего обмена местами в предыдущем просмотре,
поскольку все ключи правее места последнего обмена уже
стоят на своих окончательных местах (всплыли).
Еще одно усовершенствование – просматривать массив ключей поочередно
слева направо, а затем справа налево.
Такой метод называется шейкер – сортировкой.
Предложенные усовершенствования улучшают быстродействие,
однако время работы остается пропорциональным N2.