Сортировка пузырьком на Java — пошаговая реализация с разбором

Сортировка пузырьком (Bubble Sort) — самый простой и наглядный алгоритм сортировки массива. Идея в том, чтобы многократно проходить по массиву и менять местами соседние элементы, если они стоят в неправильном порядке. После каждого прохода самый большой (или самый маленький) элемент «всплывает» в конец массива — как пузырёк воздуха в воде. Отсюда и название.

Как работает алгоритм (по шагам):

  1. Берём первые два соседних элемента массива.

  2. Если левый больше правого — меняем их местами.

  3. Сдвигаемся на одну позицию вправо и повторяем сравнение со следующей парой.

  4. Когда дошли до конца массива — это один «проход». Самый большой элемент оказался в конце.

  5. Повторяем проходы, пока массив не станет полностью отсортированным.

Примечание

Асимптотическая сложность:

  • Время в худшем и среднем случае: O(n²) — два вложенных цикла.

  • Время в лучшем случае: O(n) — если массив уже отсортирован (с оптимизацией).

  • Память: O(1) — сортировка идёт «на месте», без дополнительных массивов.

Совет

Сортировка пузырьком хорошо подходит для обучения и для очень маленьких массивов (до 10-20 элементов). Для больших массивов лучше использовать быструю или слиянием — они работают за O(n log n).

Чтобы понять этот пример, нужно знать следующие темы Java: методы Java, цикл for в Java, массивы в Java.

Пример: программа на Java для реализации сортировки пузырьком

// import the Class
import java.util.Arrays;
import java.util.Scanner;

class Main {

  // create an object of scanner
  // to take input from the user
  Scanner input = new Scanner(System.in);

  // method to perform bubble sort
  void bubbleSort(int array[]) {
    int size = array.length;

    // for ascending or descending sort
    System.out.println("Choose Sorting Order:");
    System.out.println("1 for Ascending \n2 for Descending");
    int sortOrder = input.nextInt();

    // run loops two times
    // first loop access each element of the array
    for (int i = 0; i < size - 1; i++)

      // second loop performs the comparison in each iteration
      for (int j = 0; j < size - i - 1; j++)

        // sort the array in ascending order
        if (sortOrder == 1) {
          // compares the adjacent element
          if (array[j] > array[j + 1]) {

            // swap if left element is greater than right
            int temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
          }
        }

        // sort the array in descending order
        else {
          // compares the adjacent element
          if (array[j] < array[j + 1]) {

            // swap if left element is smaller than right
            int temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
          }
        }

  }

  // driver code
  public static void main(String args[]) {

    // create an array
    int[] data = { -2, 45, 0, 11, -9 };

    // create an object of Main class
    Main bs = new Main();

    // call the method bubbleSort using object bs
    // pass the array as the method argument
    bs.bubbleSort(data);
    System.out.println("Sorted Array in Ascending Order:");

    // call toString() of Arrays class
    // to convert data into the string
    System.out.println(Arrays.toString(data));
  }
}

Вывод 1:

Choose Sorting Order:
1 for Ascending
2 for Descending
1
Sorted Array:
[-9, -2, 0, 11, 45]

В этом случае мы ввели 1. Поэтому программа отсортировала массив по возрастанию.

Вывод 2:

Choose Sorting Order:
1 for Ascending
2 for Descending
2
Sorted Array:
[45, 11, 0, -2, -9]

В этом случае мы ввели 2. Поэтому программа отсортировала массив по убыванию.

Подсказка

Для ввода значений с клавиатуры здесь используется класс Scanner из пакета java.util. Метод Arrays.toString() удобно превращает массив в строку для вывода на экран.