1. Введение
В этой быстрой статье мы подробно рассмотрим алгоритм пузырьковой сортировки, сосредоточив внимание на реализации Java.
Это один из самых простых алгоритмов сортировки; основная идея состоит в том, чтобы продолжать менять местами соседние элементы массива, если они находятся в неправильном порядке, до тех пор, пока коллекция не будет отсортирована.
Мелкие элементы «всплывают» в верхней части списка по мере того, как мы итерируем структуру данных. Следовательно, этот метод известен как пузырьковая сортировка.
Поскольку сортировка выполняется путем замены, мы можем сказать, что она выполняет сортировку на месте.
Кроме того, если два элемента имеют одинаковые значения, порядок результирующих данных будет сохранен, что делает сортировку стабильной .
2. Методология
Как упоминалось ранее, для сортировки массива мы перебираем его, сравнивая соседние элементы и при необходимости меняя их местами. Для массива размера n мы выполняем n-1 таких итераций.
Давайте рассмотрим пример, чтобы понять методологию. Мы хотели бы отсортировать массив в порядке возрастания:
4 2 1 6 3 5
Мы начинаем первую итерацию со сравнения 4 и 2; они определенно не в надлежащем порядке. Замена приведет к:
[2 4] 1 6 3 5
Теперь повторяем то же самое для 4 и 1:
2 [1 4] 6 3 5
Продолжаем до конца:
2 1 [ **4 6]** 3 5
2 1 4 [3 6] 5
2 1 4 3 [5 6]
Как мы видим, в конце первой итерации мы получили последний элемент на своем законном месте. Теперь все, что нам нужно сделать, это повторить ту же процедуру в следующих итерациях. Кроме того, мы исключаем элементы, которые уже отсортированы.
Во второй итерации мы будем перебирать весь массив, кроме последнего элемента. Точно так же для 3-й итерации мы опускаем последние 2 элемента. Как правило, для k-й итерации мы итерируем до индекса nk (исключая). В конце n-1 итераций мы получим отсортированный массив.
Теперь, когда вы поняли технику, давайте углубимся в реализацию.
3. Реализация
Давайте реализуем сортировку для примера массива, который мы обсуждали, используя подход Java 8:
void bubbleSort(Integer[] arr) {
int n = arr.length;
IntStream.range(0, n - 1)
.flatMap(i -> IntStream.range(1, n - i))
.forEach(j -> {
if (arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
});
}
И быстрый тест JUnit для алгоритма:
@Test
public void whenSortedWithBubbleSort_thenGetSortedArray() {
Integer[] array = { 2, 1, 4, 6, 3, 5 };
Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(array);
assertArrayEquals(array, sortedArray);
}
4. Сложность и оптимизация
Как мы видим, для среднего и наихудшего случая временная сложность составляет O(n^2) .
Кроме того, пространственная сложность даже в худшем случае составляет O(1), так как алгоритм пузырьковой сортировки не требует дополнительной памяти , а сортировка происходит в исходном массиве.
Тщательно проанализировав решение, мы можем увидеть, что если в итерации не найдено ни одного обмена, нам не нужно продолжать итерацию .
В случае рассмотренного ранее примера после 2-й итерации получаем:
1 2 3 4 5 6
В третьей итерации нам не нужно менять местами никакие пары соседних элементов. Таким образом, мы можем пропустить все оставшиеся итерации.
В случае отсортированного массива в самой первой итерации подкачка не понадобится — значит, мы можем остановить выполнение. Это наилучший сценарий, и временная сложность алгоритма составляет O(n) .
Теперь давайте реализуем оптимизированное решение.
public void optimizedBubbleSort(Integer[] arr) {
int i = 0, n = arr.length;
boolean swapNeeded = true;
while (i < n - 1 && swapNeeded) {
swapNeeded = false;
for (int j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
swapNeeded = true;
}
}
if(!swapNeeded) {
break;
}
i++;
}
}
Давайте проверим вывод для оптимизированного алгоритма:
@Test
public void
givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() {
Integer[] array = { 2, 1, 4, 6, 3, 5 };
Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.optimizedBubbleSort(array);
assertArrayEquals(array, sortedArray);
}
5. Вывод
В этом уроке мы увидели, как работает пузырьковая сортировка, и как она реализована на Java. Мы также увидели, как его можно оптимизировать. Подводя итог, можно сказать, что это стабильный алгоритм с временной сложностью:
- Худший и средний случай: O(n*n), когда массив находится в обратном порядке
- Лучший случай: O(n), когда массив уже отсортирован
Алгоритм популярен в компьютерной графике из-за его способности обнаруживать небольшие ошибки при сортировке. Например, в почти отсортированном массиве нужно поменять местами только два элемента, чтобы получить полностью отсортированный массив. Пузырьковая сортировка может исправить такие ошибки (т.е. отсортировать этот массив) за линейное время.
Как всегда, код реализации этого алгоритма можно найти на GitHub .