🔥 🚀 Важно для всех, кто работает с Java! 🔥
На JavaRocks ты найдешь уникальные туториалы, практические задачи и редкие книги, которых не найти в свободном доступе. Присоединяйся к нашему Telegram-каналу JavaRocks — стань частью профессионального сообщества!
Если вы когда-либо слышали о методах сортировки в программировании, скорее всего, в первую очередь вы сталкивались с алгоритмом пузырьковой сортировки. Каждый программист знает про него (или, по крайней мере, слышал во время учебы) не потому, что это лучший алгоритм сортировки в мире, а потому, что он самый простой. Этот алгоритм обычно используют для обучения или как тестовое задание на собеседовании на должность младшего программиста Java. Алгоритм пузырьковой сортировки в Java очень прост для понимания, но эффективным его назвать нельзя. Посмотрим, что он из себя представляет.
Что такое сортировка?
Прежде всего, необходимо понять, что означает “сортировка” и что можно сортировать в программах на Java. Если можно сравнить два и более элемента или объекта по какому-то признаку, значит, их можно отсортировать по этому признаку. Например, числа по возрастанию или убыванию или слова по алфавиту. Следовательно, элементы должны быть сравнимы друг с другом. Но какие именно элементы? В Java можно сравнивать элементы коллекций. Например, отсортировать массив (Array) или список (ArrayList) чисел, строк и так далее.
Как работает пузырьковая сортировка
Допустим, нужно отсортировать массив целых чисел по возрастанию, то есть от наименьшего к наибольшему.
Сначала мы проходим по всему массиву и сравниваем каждый элемент с соседним. Если порядок неправильный (слева число больше, чем справа) — меняем их местами. После первого круга в самом конце массива оказывается самый большой элемент. Можно сказать, что самый большой элемент “всплывает”. Именно поэтому алгоритм называется пузырьковой сортировкой (bubble sort).
Дальше повторяем шаг с начала до предпоследнего элемента. На предпоследнее место выходит второй по величине элемент. И так далее. Алгоритм можно немного улучшить: если на очередном проходе не произошло ни одной перестановки, значит, массив уже отсортирован, и дальше можно не продолжать.
Пример пузырьковой сортировки
Отсортируем массив целых чисел, показанный ниже на рисунке.
Шаг 1: проходим по массиву. Алгоритм начинает с первых двух элементов (с индексами 0 и 1), 8 и 7, и проверяет, в правильном ли порядке они расположены. Очевидно, что 8 > 7, поэтому мы меняем их местами. Далее смотрим на второй и третий элементы (индексы 1 и 2), теперь это 8 и 1. По тем же причинам мы меняем их местами. Потом сравниваем 8 и 2, а затем 8 и 5. Всего сделали четыре перестановки: (8, 7), (8, 1), (8, 2) и (8, 5). Значение 8 (самое большое в этом массиве) “всплыло” в конец списка и оказалось на своем месте.
Результатом первого шага пузырьковой сортировки является следующий массив:
Шаг 2. Проделываем те же действия с парами чисел (7,1), (7,2) и (7,5). Теперь 7 находится на предпоследнем месте, его не нужно сравнивать с “хвостом” списка, так как он уже отсортирован.
Результатом второго шага пузырьковой сортировки является следующий массив:
Как можно заметить, массив уже отсортирован. Тем не менее алгоритм пузырьковой сортировки выполнит еще один цикл.
Шаг 3. Проходим по массиву еще раз. Менять больше нечего, поэтому, если используется “улучшенный” вариант пузырьковой сортировки (с проверкой, была ли хотя бы одна замена на предыдущем шаге), этот шаг будет последним.
Код пузырьковой сортировки на Java
Реализация пузырьковой сортировки на Java
Напишем два метода для пузырьковой сортировки. Первый, bubbleSort(int[] myArray), является базовым. Он каждый раз проходит по всему массиву. Второй, optimizedBubbleSort(int myArray[]) — оптимизированный: алгоритм останавливается, если внутри цикла не было ни одной перестановки. Переменная counter показывает, сколько шагов было сделано при сортировке. Вот как будет выглядеть реализация пузырьковой сортировки:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}И вот что мы получим на выходе:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]Насколько эффективна пузырьковая сортировка?
Пузырьковая сортировка — один из самых простых для реализации алгоритмов, но не самый эффективный. Для его работы нужны два вложенных цикла. Даже в оптимизированной версии в худшем случае (когда элементы массива расположены в порядке, обратном желаемому) внешний цикл выполняется для каждого из n элементов. Внутренний цикл проходит n раз в первый проход, (n-1) раз во второй и так далее.
Следовательно, чтобы отсортировать все n элементов, потребуется выполнить примерно n × (n-1) / 2 итераций. Это соответствует временной сложности О(n2) и означает, что алгоритм выполняет около 500 000 сравнений для 1000 элементов массива. Однако пузырьковая сортировка достаточно эффективна в использовании памяти (сложность O(n)) и хорошо подходит для небольших массивов, которые почти уже отсортированы.
Итак, вы узнали, как работает пузырьковая сортировка: переставляйте соседние элементы, пока весь список не будет отсортирован. Просто, правда? Но возникает вполне логичный вопрос: “Насколько эффективен этот алгоритм?”. Отличный вопрос! Давайте подробнее рассмотрим временную и пространственную сложность пузырьковой сортировки и посмотрим, как она выглядит в сравнении с другими алгоритмами сортировки.
Анализ временной сложности пузырьковой сортировки
Временная сложность показывает, как время выполнения алгоритма зависит от размера входных данных. Разберем по случаям:
Лучший случай (O(n))
Представим, что массив уже отсортирован. Пузырьковая сортировка все равно должна пройти по списку, чтобы убедиться, что перестановки не нужны. Но в оптимизированной версии, которая останавливается, если перестановок не было, это занимает всего O(n) времени.
Средний случай (O(n²))
Для случайно упорядоченного массива алгоритм должен многократно сравнивать и переставлять элементы, что приводит к временной сложности O(n²) . Это происходит потому, что каждый элемент сравнивается со всеми остальными.
Худший случай (O(n²))
В ситуации, когда массив отсортирован в обратном порядке, сортировка пузырьком выполняет максимальное количество перестановок. Это также приводит к сложности O(n²).
Итоговая таблица временной сложности
| Сценарий | Временная сложность |
|---|---|
| Лучший случай (массив рассортирован) | O(n) |
| Средний случай | O(n²) |
| Худший случай (в обратном порядке) | O(n²) |
Анализ пространственной сложности пузырьковой сортировки
А теперь поговорим о памяти. Сколько дополнительной памяти использует пузырьковая сортировка?
Ответ: O(1) вспомогательной памяти. Пузырьковая сортировка только переставляет элементы местами и не требует дополнительных массивов или структур данных. Здорово, правда?
Почему сложность O(1)?
- используются лишь несколько вспомогательных переменных для обмена;
- не создаются новые массивы или объекты.
Таким образом, пузырьковая сортировка эффективна по памяти, но не по времени. Так что, хоть она и не съест всю оперативную память, процессор нагрузит!
Сравнение пузырьковой сортировки с другими алгоритмами сортировки
Пузырьковая сортировка — не единственный алгоритм сортировки. Сравним ее с другими популярными алгоритмами и посмотрим, насколько она хороша.
Пузырьковая сортировка против сортировки вставками
- Лучший случай: и пузырьковая сортировка, и сортировка вставками имеют O(n) при оптимизации.
- Средний/худший случай: оба варианта имеют сложность O(n²) , но сортировка вставками обычно эффективнее, поскольку осуществляется меньше перестановок.
Пузырьковая сортировка против сортировки слиянием
- Временная сложность: сортировка слиянием стабильно выполняется за O(n log n) , что значительно быстрее пузырьковой сортировки.
- Пространственная сложность: сортировка слиянием использует O(n) дополнительной памяти, тогда как пузырьковая сортировка использует O(1) .
Пузырьковая сортировка против быстрой сортировки
- Лучший/средний случай: быстрая сортировка выполняется за O(n log n) .
- Худший случай: быстрая сортировка может снизиться до O(n²) при неудачной реализации, но в большинстве случаев она все равно быстрее пузырьковой сортировки.
Итоговая сравнительная таблица
| Алгоритм | Лучший случай | Средний случай | Худший случай | Пространственная сложность |
|---|---|---|---|---|
| Пузырьковая сортировка | O(n) | O(n²) | O(n²) | O(1) |
| Сортировка вставками | O(n) | O(n²) | O(n²) | O(1) |
| Сортировка слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Быстрая сортировка | O(n log n) | O(n log n) | O(n²) | O(log n) |
Когда следует использовать пузырьковую сортировку?
Учитывая ее производительность, вы, вероятно, думаете: «А нужна ли вообще пузырьковая сортировка?» Ответ: и да, и нет.
Когда использовать пузырьковую сортировку:
- при работе с очень маленькими массивами;
- в образовательных целях, чтобы понять, как работают алгоритмы сортировки;
- когда простота важнее производительности.
Когда следует избегать пузырьковой сортировки:
- для больших массивов — лучше применять сортировку слиянием, быструю сортировку или встроенные методы сортировки Java;
- когда производительность имеет решающее значение.
Перевод статьи «Bubble Sort Java».