Сортировка пузырьком  —  не самый быстрый алгоритм сортировки, но обычно именно его первым изучают студенты по специальности «Информатика», и неспроста. Освоив его подход, легче понять принцип работы алгоритмов сортировки на фундаментальном уровне. Изучим, как реализовать его на C++ эффективно.

Базовый алгоритм

При пузырьковой сортировке многократно проходится список, соседние элементы сравниваются и, если расположены в неправильном порядке, меняются местами. Вот простейшая реализация:

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Разберем подробнее:

  1. Внешний цикл выполняется n-1 раз.
  2. Внутренним циклом сравниваются соседние элементы.
  3. Если элемент больше следующего, они меняются местами.

Оптимизированная реализация

Базовая версия  —  рабочая, но мы сделаем ее более эффективной. Вот оптимизированная версия: если массив уже отсортирован, она завершается раньше:

void bubbleSortOptimized(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        
        // Если перемен мест не случилось, массив уже отсортирован
        if (!swapped) {
            break;
        }
    }
}

Оптимизация выполняется за счет отслеживания, не случилось ли перестановок во время прохождения. Если их не было, массив отсортирован и сортировка завершается.

Версия template для любого типа данных

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

template<typename T>
void bubbleSort(std::vector<T>& arr) {
    int n = arr.size();
    bool swapped;
    
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Реальные применения

1. Сортировка пользовательских объектов

class Student {
private:
    std::string name;
    float gpa;
    
public:
    Student(std::string n, float g) : name(std::move(n)), gpa(g) {}
    
    // Методы-получатели
    const std::string& getName() const { return name; }
    float getGPA() const { return gpa; }
    
    // Оператор сравнения для сортировки
    bool operator>(const Student& other) const {
        return gpa > other.gpa;
    }
};

void sortStudentsByGPA() {
    std::vector<Student> students = {
        Student("Alice", 3.8),
        Student("Bob", 3.5),
        Student("Charlie", 3.9)
    };
    
    bubbleSort(students);  // Используется версия «template»
    
    // Выводятся отсортированные результаты
    for (const auto& student : students) {
        std::cout << student.getName() << ": " 
                  << student.getGPA() << "\n";
    }
}

2. Сортировка с пользовательскими компараторами

template<typename T, typename Compare>
void bubbleSort(std::vector<T>& arr, Compare comp) {
    int n = arr.size();
    bool swapped;
    
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (comp(arr[j], arr[j + 1])) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

// Пример применения с пользовательским компаратором
void sortWithCustomRules() {
    std::vector<Student> students = {
        Student("Alice", 3.8),
        Student("Bob", 3.5),
        Student("Charlie", 3.9)
    };
    
    // Сортируются по длине имени
    bubbleSort(students, [](const Student& a, const Student& b) {
        return a.getName().length() > b.getName().length();
    });
}

3. Визуальное отображение сортировки

class SortVisualizer {
private:
    std::vector<int> data;
    static const int DELAY_MS = 100;
    
    void clearScreen() {
        std::cout << "\033[2J\033[1;1H";  // Управляющие символы ANSI
    }
    
    void drawBars() {
        for (int num : data) {
            std::cout << std::string(num, '#') << '\n';
        }
        std::this_thread::sleep_for(
            std::chrono::milliseconds(DELAY_MS)
        );
    }
    
public:
    SortVisualizer(std::vector<int> arr) : data(std::move(arr)) {}
    
    void visualBubbleSort() {
        int n = data.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    std::swap(data[j], data[j + 1]);
                    clearScreen();
                    drawBars();
                }
            }
        }
    }
};

Анализ производительности

Измерим, как выполняется сортировка пузырьком при разных размерах входных данных:

class SortAnalyzer {
private:
    static std::vector<int> generateRandomArray(int size) {
        std::vector<int> arr(size);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, 1000);
        
        for (int& num : arr) {
            num = dis(gen);
        }
        return arr;
    }
    
public:
    static void analyzeBubbleSort() {
        std::vector<int> sizes = {100, 1000, 10000};
        
        for (int size : sizes) {
            auto arr = generateRandomArray(size);
            
            auto start = std::chrono::high_resolution_clock::now();
            bubbleSort(arr);
            auto end = std::chrono::high_resolution_clock::now();
            
            auto duration = std::chrono::duration_cast<
                std::chrono::milliseconds
            >(end - start);
            
            std::cout << "Size " << size << ": " 
                      << duration.count() << "ms\n";
        }
    }
};

Типичные проблемы и их решения

1. Лишние сравнения

// Плохо: даже после того, как массив отсортирован, сравнения продолжаются
void inefficientBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1; j++) {  // Неверно: должно быть «n–1–i»
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Хорошо: при каждом проходе сравнения сокращаются
void efficientBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

2. Управление памятью с указателями

// Безопасная версия для массивов указателей
template<typename T>
void bubbleSortPointers(std::vector<T*>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            // Безопасно разыменовываются указатели
            if (*arr[j] > *arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Сортировка пузырьком в коде на продакшене обычно не используется, так как std::sort предпочтительнее. Тем не менее, понимая эти принципы работы, проще освоить алгоритмы сортировки в целом. Рассмотренные здесь концепции  —  сравнение элементов, перестановка значений, оптимизация на основе состояния массива  —  применимы и к алгоритмам сортировки посложнее.

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

Читайте также:

Читайте нас в Telegram, VK и Дзен

Перевод статьи ryan: Bubble Sort in C++: Complete Guide

Предыдущая статьяРазработка игр для малышей: больше пользы, меньше разочарования