CodeUtility
Кодить проще - жить легче!
Алгоритмы C/C++

Сортировка пузырьком (bubble sort) в C и C++

В этом уроке вы реализуете сортировку пузырьком, раз за разом меняя местами соседние элементы, стоящие в неправильном порядке.

Введение

Сортировка пузырьком несколько раз проходит по массиву, сравнивает каждую пару соседних элементов и меняет их местами, если порядок неверный. За каждый проход наибольшее из ещё не отсортированных значений постепенно перемещается к концу массива.

Главное

  • Проверяйте на пустом вводе, одном элементе, повторах и уже отсортированных данных.
  • Сначала добейтесь правильной работы кода, а потом оптимизируйте.
  • В реальном коде отдавайте предпочтение готовым функциям стандартной библиотеки.

Визуализация: Сортировка пузырьком (bubble sort) в C и C++

O(n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>

int main(void) {
    int values[] = {5, 1, 4, 2};
    for (int end = 3; end > 0; --end) {
        int changed = 0;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                int temporary = values[index];
                values[index] = values[index + 1];
                values[index + 1] = temporary;
                changed = 1;
            }
        }
        if (!changed) break;
    }
    for (int index = 0; index < 4; ++index) {
        printf("%d ", values[index]);
    }
}
Результат выполнения
1 2 4 5
C++
Запустить →
main.cpp
#include <iostream>
#include <vector>

int main() {
    std::vector values{5, 1, 4, 2};
    for (auto end = values.end(); end != values.begin(); --end) {
        bool changed = false;
        for (auto item = values.begin(); item + 1 != end; ++item) {
            if (*item > *(item + 1)) {
                std::iter_swap(item, item + 1);
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Результат выполнения
1 2 4 5

Сравнение C и C++

Переменная changed показывает, был ли за проход хотя бы один обмен. Если обменов не было, массив уже отсортирован и цикл останавливается раньше, поэтому уже отсортированный массив стоит всего O(n). В худшем случае алгоритму нужно O(n²), поэтому он нужен в основном для обучения. На практике в C++ обычно используют std::sort.

C

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Пройдите каждое сравнение на бумаге.
  • Проверьте на повторах и на очень больших и очень маленьких значениях.
  • Измерьте время работы своего кода и сравните его со стандартной библиотекой.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи