Перейти к содержанию

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

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

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

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

bubble_operation_step2

bubble_operation_step3

bubble_operation_step4

bubble_operation_step5

bubble_operation_step6

bubble_operation_step7

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

11.3.1   Алгоритм

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

  1. Сначала выполнить один проход "всплытия" по \(n\) элементам, переместив максимальный элемент массива на правильную позицию.
  2. Затем выполнить "всплытие" по оставшимся \(n - 1\) элементам, переместив второй по величине элемент на правильную позицию.
  3. Продолжать по аналогии; после \(n - 1\) раундов "всплытия" первые \(n - 1\) по величине элементы окажутся на правильных позициях.
  4. Оставшийся единственный элемент обязательно является минимальным, сортировать его уже не нужно, поэтому сортировка завершена.

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

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

Пример кода:

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)\) .

bubble_sort.py
def bubble_sort_with_flag(nums: list[int]):
    """Пузырьковая сортировка (оптимизация флагом)"""
    n = len(nums)
    # Внешний цикл: неотсортированный диапазон [0, i]
    for i in range(n - 1, 0, -1):
        flag = False  # Инициализировать флаг
        # Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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]
                flag = True  # Записать обмен элементов
        if not flag:
            break  # На этой итерации «всплытия» не было ни одного обмена, сразу выйти
bubble_sort.cpp
/* Пузырьковая сортировка (оптимизация флагом) */
void bubbleSortWithFlag(vector<int> &nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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]);
                flag = true; // Записать обмен элементов
            }
        }
        if (!flag)
            break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
bubble_sort.java
/* Пузырьковая сортировка (оптимизация флагом) */
void bubbleSortWithFlag(int[] nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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;
                flag = true; // Записать обмен элементов
            }
        }
        if (!flag)
            break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
bubble_sort.cs
/* Пузырьковая сортировка (оптимизация флагом) */
void BubbleSortWithFlag(int[] nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = nums.Length - 1; i > 0; i--) {
        bool flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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]);
                flag = true;  // Записать обмен элементов
            }
        }
        if (!flag) break;     // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
bubble_sort.go
/* Пузырьковая сортировка (оптимизация флагом) */
func bubbleSortWithFlag(nums []int) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i := len(nums) - 1; i > 0; i-- {
        flag := false // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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]
                flag = true // Записать обмен элементов
            }
        }
        if flag == false { // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
            break
        }
    }
}
bubble_sort.swift
/* Пузырьковая сортировка (оптимизация флагом) */
func bubbleSortWithFlag(nums: inout [Int]) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i in nums.indices.dropFirst().reversed() {
        var flag = false // Инициализировать флаг
        for j in 0 ..< i {
            if nums[j] > nums[j + 1] {
                // Поменять местами nums[j] и nums[j + 1]
                nums.swapAt(j, j + 1)
                flag = true // Записать обмен элементов
            }
        }
        if !flag { // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
            break
        }
    }
}
bubble_sort.js
/* Пузырьковая сортировка (оптимизация флагом) */
function bubbleSortWithFlag(nums) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (let i = nums.length - 1; i > 0; i--) {
        let flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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;
                flag = true; // Записать обмен элементов
            }
        }
        if (!flag) break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
bubble_sort.ts
/* Пузырьковая сортировка (оптимизация флагом) */
function bubbleSortWithFlag(nums: number[]): void {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (let i = nums.length - 1; i > 0; i--) {
        let flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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;
                flag = true; // Записать обмен элементов
            }
        }
        if (!flag) break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
bubble_sort.dart
/* Пузырьковая сортировка (оптимизация флагом) */
void bubbleSortWithFlag(List<int> nums) {
  // Внешний цикл: неотсортированный диапазон [0, i]
  for (int i = nums.length - 1; i > 0; i--) {
    bool flag = false; // Инициализировать флаг
    // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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;
        flag = true; // Записать обмен элементов
      }
    }
    if (!flag) break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
  }
}
bubble_sort.rs
/* Пузырьковая сортировка (оптимизация флагом) */
fn bubble_sort_with_flag(nums: &mut [i32]) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for i in (1..nums.len()).rev() {
        let mut flag = false; // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [0, i] в его правый конец
        for j in 0..i {
            if nums[j] > nums[j + 1] {
                // Поменять местами nums[j] и nums[j + 1]
                nums.swap(j, j + 1);
                flag = true; // Записать обмен элементов
            }
        }
        if !flag {
            break; // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
        };
    }
}
bubble_sort.c
/* Пузырьковая сортировка (оптимизация флагом) */
void bubbleSortWithFlag(int nums[], int size) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (int i = size - 1; i > 0; i--) {
        bool flag = false;
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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;
                flag = true;
            }
        }
        if (!flag)
            break;
    }
}
bubble_sort.kt
/* Пузырьковая сортировка (оптимизация флагом) */
fun bubbleSortWithFlag(nums: IntArray) {
    // Внешний цикл: неотсортированный диапазон [0, i]
    for (i in nums.size - 1 downTo 1) {
        var flag = false // Инициализировать флаг
        // Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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
                flag = true // Записать обмен элементов
            }
        }
        if (!flag) break // На этой итерации «всплытия» не было ни одного обмена, сразу выйти
    }
}
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

# ## Пузырьковая сортировка (оптимизация флагом) ###
def bubble_sort_with_flag(nums)
  n = nums.length
  # Внешний цикл: неотсортированный диапазон [0, i]
  for i in (n - 1).downto(1)
    flag = false # Инициализировать флаг

    # Внутренний цикл: переместить максимальный элемент неотсортированного диапазона [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]
        flag = true # Записать обмен элементов
      end
    end

    break unless flag # На этой итерации «всплытия» не было ни одного обмена, сразу выйти
  end
end
Визуализация кода

11.3.3   Характеристики алгоритма

  • Временная сложность равна \(O(n^2)\), алгоритм адаптивен: длины диапазонов, проходящих "всплытие" в разных раундах, последовательно равны \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\) , а их сумма равна \((n - 1) n / 2\) . После добавления оптимизации с flag лучшая временная сложность может достигать \(O(n)\) .
  • Пространственная сложность равна \(O(1)\), сортировка выполняется на месте: указатели \(i\) и \(j\) используют константный объем дополнительной памяти.
  • Стабильная сортировка: поскольку при "всплытии" равные элементы не обмениваются местами.
Оставляйте свои идеи, вопросы и предложения в комментариях