11.3 Сортировка пузырьком¶

Сортировка пузырьком (bubble sort) реализует сортировку путем последовательного сравнения и обмена соседних элементов. Этот процесс напоминает всплытие пузырьков снизу вверх, откуда и произошло название алгоритма.

Как показано на рисунке 11-4, процесс «всплытия» можно смоделировать через операцию обмена элементов: начиная от левого края массива и двигаясь вправо, мы последовательно сравниваем соседние элементы и, если «левый элемент > правый элемент», меняем их местами. После завершения прохода максимальный элемент будет перемещен в самый правый конец массива.

Рисунок 11-4 Моделирование пузырька через обмен элементов

11.3.1 Алгоритм¶

Пусть длина массива равна $n$ . Тогда шаги сортировки пузырьком показаны на рисунке 11-5.

Сначала выполнить один проход «всплытия» по $n$ элементам, переместив максимальный элемент массива на правильную позицию.
Затем выполнить «всплытие» по оставшимся $n - 1$ элементам, переместив второй по величине элемент на правильную позицию.
Продолжать по аналогии. После $n - 1$ раундов «всплытия» первые $n - 1$ по величине элементы окажутся на правильных позициях.
Оставшийся единственный элемент обязательно является минимальным, сортировать его уже не нужно, поэтому сортировка завершена.

Процесс сортировки пузырьком

Рисунок 11-5 Процесс сортировки пузырьком

Пример кода:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

bubble_sort.py


def bubble_sort(nums: list[int]):
    """Пузырьковая сортировка"""
    n = len(nums)
    # Внешний цикл: неотсортированный диапазон [0, i]
    for i in range(n - 1, 0, -1):
        # Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # Поменять местами nums[j] и nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

bubble_sort.cpp


/* Пузырьковая сортировка */
void bubbleSort(vector<int> &nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                // Здесь используется функция std::swap()
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}

bubble_sort.java


/* Пузырьковая сортировка */
void bubbleSort(int[] nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

bubble_sort.cs


/* Пузырьковая сортировка */
void BubbleSort(int[] nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.Length - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                (nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
            }
        }
    }
}

bubble_sort.go


/* Пузырьковая сортировка */
func bubbleSort(nums []int) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i := len(nums) - 1; i > 0; i-- {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for j := 0; j < i; j++ {
            if nums[j] > nums[j+1] {
                // Поменять местами nums[j] и nums[j + 1]
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
}

bubble_sort.swift


/* Пузырьковая сортировка */
func bubbleSort(nums: inout [Int]) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i in nums.indices.dropFirst().reversed() {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for j in 0 ..< i {
            if nums[j] > nums[j + 1] {
                // Поменять местами nums[j] и nums[j + 1]
                nums.swapAt(j, j + 1)
            }
        }
    }
}

bubble_sort.js


/* Пузырьковая сортировка */
function bubbleSort(nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (let i = nums.length - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

bubble_sort.ts


/* Пузырьковая сортировка */
function bubbleSort(nums: number[]): void {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (let i = nums.length - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

bubble_sort.dart


/* Пузырьковая сортировка */
void bubbleSort(List<int> nums) {
  // Внешний цикл: неотсортированный диапазон [0, i]
  for (int i = nums.length - 1; i > 0; i--) {
    // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
    for (int j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        // Поменять местами nums[j] и nums[j + 1]
        int tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
  }
}

bubble_sort.rs


/* Пузырьковая сортировка */
fn bubble_sort(nums: &mut [i32]) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i in (1..nums.len()).rev() {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for j in 0..i {
            if nums[j] > nums[j + 1] {
                // Поменять местами nums[j] и nums[j + 1]
                nums.swap(j, j + 1);
            }
        }
    }
}

bubble_sort.c


/* Пузырьковая сортировка */
void bubbleSort(int nums[], int size) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = size - 1; i > 0; i--) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

bubble_sort.kt


/* Пузырьковая сортировка */
fun bubbleSort(nums: IntArray) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (i in nums.size - 1 downTo 1) {
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for (j in 0..<i) {
            if (nums[j] > nums[j + 1]) {
                // Поменять местами nums[j] и nums[j + 1]
                val temp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = temp
            }
        }
    }
}

bubble_sort.rb


### Пузырьковая сортировка ###
def bubble_sort(nums)
  n = nums.length
  # Внешний цикл: неотсортированный диапазон [0, i]
  for i in (n - 1).downto(1)
    # Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
    for j in 0...i
      if nums[j] > nums[j + 1]
        # Поменять местами nums[j] и nums[j + 1]
        nums[j], nums[j + 1] = nums[j + 1], nums[j]
      end
    end
  end
end

Визуализация кода

Во весь экран >

11.3.2 Оптимизация эффективности¶

Если в каком-либо раунде «всплытия» не произошло ни одного обмена, значит, массив уже отсортирован и можно сразу вернуть результат. Поэтому можно добавить флаг flag для отслеживания этой ситуации и немедленного выхода.

После такой оптимизации худшая и средняя временные сложности сортировки пузырьком по-прежнему равны $O (n^{2})$ . Однако если входной массив уже полностью упорядочен, достигается лучшая временная сложность $O (n)$ .