В этой статье мы рассмотрим пример программы сортировки массива или списка элементов с помощью алгоритма пузырьковой сортировки.
Пузырьковая сортировка. Теория
Алгоритм пузырьковой сортировки является одним из самых простых в реализации и самых медленных по времени выполнения. Его суть сводится к поочередному сравниванию соседних элементов массива.
Поочередное сравнивание соседних элементов массива
Пример реализации пузырьковой сортировки на Java
Ниже представлена небольшая программа на Java, демонстрирующая «всю мощь» пузырьковой сортировки.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
package ua.com.prologistic; import java.util.Arrays; import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { int counter, num, array[]; //Создаем объект Scanner для считывания чисел, введенных пользователем Scanner input = new Scanner(System.in); System.out.println("Введите количество элементов массива: "); num = input.nextInt(); // Создаем массив введенного пользователем размера array = new int[num]; System.out.println("Введите " + num + " чисел"); //Заполняем массив, вводя элементы в консоль for (counter = 0; counter < num; counter++) { array[counter] = input.nextInt(); } // печатаем массив перед пузырьковой сортировкой System.out.println("массив перед пузырьковой сортировкой : " + Arrays.toString(array)); // сортируем массив bubbleSort(array); // печатаем массив после пузырьковой сортировки System.out.println("массив после пузырьковой сортировки : " + Arrays.toString(array)); } // метод пузырьковой сортировки public static void bubbleSort(int[] num) { int j; boolean flag = true; // устанавливаем наш флаг в true для первого прохода по массиву int temp; // вспомогательная переменная while (flag) { flag = false; // устанавливаем флаг в false в ожидании возможного свопа (замены местами) for (j = 0; j < num.length - 1; j++) { if (num[j] < num[j + 1]) { // измените на > для сортировки по возрастанию temp = num[j]; // меняем элементы местами num[j] = num[j + 1]; num[j + 1] = temp; flag = true; // true означает, что замена местами была проведена } } } } } |
Следует отметить, что пузырьковая сортировка будет продолжаться, пока будут перестановки элементов местами, то есть пока массив не будет полностью отсортирован.
Результат выполнения пузырьковой сортировки на Java по убыванию:
1 2 3 4 5 6 7 8 9 10 |
Введите количество элементов массива: 5 Введите 5 чисел 2 6 4 12 89 массив перед пузырьковой сортировкой : [2, 6, 4, 12, 89] массив после пузырьковой сортировки : [89, 12, 6, 4, 2] |
Также стоит заметить, что наша программа сортирует элементы по убыванию, то есть от большего к меньшему. Чтобы пузырьковый алгоритм сортировал по возрастанию (от меньшего к большему), вам нужно изменить в условии сортировки знак <
на >
:
1 |
if (num[j] < num[j + 1]) |
на
1 |
if (num[j] > num[j + 1]) |
Результат выполнения пузырьковой сортировки на Java по возрастанию:
1 2 3 4 5 6 7 8 9 10 |
Введите количество элементов массива: 5 Введите 5 чисел 87 2 75 4 1 массив перед пузырьковой сортировкой : [87, 2, 75, 4, 1] массив после пузырьковой сортировки : [1, 2, 4, 75, 87] |
Вот такая у нас получилась реализация алгоритма пузырьковой сортировки на Java. Напомню, эта статья является частью раздела Java для начинающих. Следите за обновлениями.
А зачем за каждый проход проходит по всему массиву. Разве самый большой(маленький) элемент не оказывается в конце массива, т.е. на своем месте за один проход? Тогда нужно каждый следущий проход делать до n-i элемента. Где n- номер последнего элемента, i — номер прохода. Сложность алгоритма значительно уменьшается.
Спасибо вам за очень хороший пример пузырьковой сортировки
Выполнив сортировку, метод продолжает бесконечно выполнять цикл проверяя числа