Идея, лежащая в основе сортировки «методом пузырька» заключается в следующем. Файл просматривается несколько раз последовательно. Каждый просмотр состоит из сравнения каждого элемента xi файла со следующим за ним элементом xi+1 и «обмена» (транспозиции) этих элементов, если они располагаются не в нужном порядке [3].
Например, задан файл 25, 57, 48, 37, 12, 92, 86, 33. Требуется отсортировать записи, расположив их по возрастанию значений элементов файла. Действия сортировки оформим в виде таблицы.
Итерация
Файл
0
25, 57, 48, 37, 12, 92, 86, 33
25, 48, 37, 12, 57, 86, 33, 92
25, 37, 12, 48, 57, 33, 86, 92
25, 12, 37, 48, 33, 57 ,86, 92
12, 25, 37, 33, 48, 57, 86, 92
12, 25, 33, 37, 48, 57, 86, 92
Эффективность «метода пузырька» считается следующим образом. Имеется в худшем случае n–1 просмотров файла и n–1 сравнений в каждом просмотре. Таким, образом, общее число сравнений равно (n–1) (n–1) = n2 – 2n +1, что составляет »n2.
Единственным плюсом «метода пузырька» является то, что для такой сортировки требуется мало дополнительного пространства (одна дополнительная запись для временного хранения той записи, для которой выполняется транспозиция, и несколько простых целых переменных).
0
25, 12, 37, 48, 33, 57 ,86, 92
12, 25, 37, 33, 48, 57, 86, 92