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-й итерации мы выполняем итерацию до индекса n-k (исключено). В конце 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 .