«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), когда массив уже sorted

Алгоритм популярен в компьютерной графике из-за его способности обнаруживать небольшие ошибки при сортировке. Например, в почти отсортированном массиве нужно поменять местами только два элемента, чтобы получить полностью отсортированный массив. Пузырьковая сортировка может исправить такие ошибки (т.е. отсортировать этот массив) за линейное время.

Как всегда, код реализации этого алгоритма можно найти на GitHub.