Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

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

    Оглавление:

    На физкультуре учитель просит класс выстроиться по росту, от самого низкого к самому высокому, но сам никого не переставляет. Правило одно: сравни свой рост с соседом справа и, если ты выше, поменяйтесь местами. Пара за парой ребята проходят по шеренге от начала до конца, и самый высокий оказывается последним. Еще несколько таких проходов — и шеренга выстроена.

    Так работает сортировка пузырьком — самый простой алгоритм сортировки. Большие элементы постепенно «всплывают» в конец массива, как пузырьки воздуха в воде.

    Идея алгоритма

    Идем по массиву слева направо и сравниваем соседние элементы a[j] и a[j + 1]. Если левый больше правого, меняем их местами. Это один проход. После первого прохода самый большой элемент стоит в конце, после второго на свое место встает второй по величине, и так далее. Для массива из $n$ элементов хватает $n - 1$ проходов: когда на местах все, кроме одного, этот последний тоже стоит правильно.

    Ключевая идея: После $k$-го прохода последние $k$ элементов уже стоят на своих местах. Поэтому каждый следующий проход можно делать на одно сравнение короче.

    Разбор на примере

    Отсортируем массив [4, 2, 5, 1, 3]. Первый проход подробно:

    1. 4 > 2 — меняем: [2, 4, 5, 1, 3].
    2. 4 < 5 — оставляем.
    3. 5 > 1 — меняем: [2, 4, 1, 5, 3].
    4. 5 > 3 — меняем: [2, 4, 1, 3, 5]. Пятерка «всплыла» в конец.

    Остальные проходы устроены так же, только каждый на одно сравнение короче:

    Проход Сравнений Обменов Массив после прохода
    1 4 3 [2, 4, 1, 3, 5]
    2 3 2 [2, 1, 3, 4, 5]
    3 2 1 [1, 2, 3, 4, 5]
    4 1 0 [1, 2, 3, 4, 5]

    После третьего прохода массив уже отсортирован, и в четвертом не случилось ни одного обмена. Отсюда полезное улучшение: если за проход не было обменов, массив упорядочен, и дальше можно не проверять. Для почти отсортированного массива, например [1, 2, 4, 3, 5], хватит двух проходов вместо четырех: первый поменяет 4 и 3, второй убедится, что все на местах.

    Реализация

    Переменная swapped запоминает, был ли обмен за проход. Внутренний цикл идет до n - 1 - i: последние i элементов уже на местах.

    def bubble_sort(a):
        n = len(a)
        for i in range(n - 1):
            swapped = False
            for j in range(n - 1 - i):
                if a[j] > a[j + 1]:
                    a[j], a[j + 1] = a[j + 1], a[j]  # меняем соседей местами
                    swapped = True
            if not swapped:  # обменов не было - массив отсортирован
                break
    
    
    nums = [4, 2, 5, 1, 3]
    bubble_sort(nums)
    print(nums)  # [1, 2, 3, 4, 5]
    

    На C++ для обмена есть готовая функция swap:

    #include <iostream>
    #include <utility>
    #include <vector>
    using namespace std;
    
    void bubbleSort(vector<int>& a) {
        int n = a.size();
        for (int i = 0; i < n - 1; i++) {
            bool swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a[j], a[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
    
    int main() {
        vector<int> a = {4, 2, 5, 1, 3};
        bubbleSort(a);
        for (int x : a) cout << x << " ";  // 1 2 3 4 5
        cout << "\n";
    }
    

    Сложность

    Хуже всего, когда массив отсортирован в обратном порядке: каждое сравнение заканчивается обменом, и ранний выход не срабатывает. Сравнений будет

    $$(n - 1) + (n - 2) + \ldots + 1 = \frac{n(n - 1)}{2}$$

    Это $O(n^2)$: для 1000 элементов — 499 500 сравнений. Лучший случай — массив уже отсортирован: хватит одного прохода из $n - 1$ сравнений, то есть $O(n)$. Дополнительной памяти почти не нужно, только переменная для обмена — $O(1)$.

    Массив Сравнений Обменов Сложность
    Уже отсортирован $n - 1$ 0 $O(n)$
    Случайный порядок до $\frac{n(n - 1)}{2}$ в среднем $\frac{n(n - 1)}{4}$ $O(n^2)$
    Отсортирован наоборот $\frac{n(n - 1)}{2}$ $\frac{n(n - 1)}{2}$ $O(n^2)$

    Пузырек — учебный алгоритм. В настоящих программах сортируют встроенными средствами: sorted(a) или a.sort() в Python и sort(a.begin(), a.end()) в C++. Они работают за $O(n \log n)$ и на миллионе чисел делают в десятки тысяч раз меньше операций, чем пузырек.

    Частая ошибка: Внутренний цикл до n вместо n - 1 - i. На последнем шаге a[j + 1] выходит за конец массива: Python выдаст ошибку IndexError, а C++ может молча прочитать чужую память и выдать мусор. Еще одна ловушка — сравнение >= вместо >: равные элементы начнут меняться местами впустую.

    Проверь себя

    1.

    Где окажется самый большой элемент массива после первого прохода сортировки пузырьком?

    2.

    Сколько обменов сделает сортировка пузырьком, чтобы упорядочить массив [4, 1, 3, 2]?

    3.

    Соедини характеристику сортировки пузырьком и ее значение.

    Сложность в худшем случае

    $O(n)$

    Сложность на уже отсортированном массиве

    $O(1)$

    Дополнительная память

    10

    Сравнений в худшем случае при $n = 5$

    $O(n^2)$

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами