Метод пузырька

Название этого метода произошло от известного физического явления – пузырек воздуха

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

Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то

меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать

При следующем проходе наша задача – поставить на место элемент A[1]. Делаем это так же,но уже не рассматриваем A[0], который стоит на своем месте. Сделав N-1проходов, мы установим на место элементы с A[0]по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет).

Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз(метод имеет порядок N2). К сожалению, все простые алгоритмы сортировки имеют такой(квадратичный) порядок.