Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Сортировка пузырьком - алгоритм состоит в повторяющихся проходах по сортируемому массиву.

---

Принцип работы алгоритма

На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более n−1 проходов, где n размер массива, чтобы отсортировать массив. Иначе - алгоритм переходит к следующему элементу.

---

Схематическая работа алгоритма

Есть неотсортированная последовательность данных

Первый элемент последовательности - 5, 5 > 1 следовательно меняем местами.

На следующей итерации 5 меняется с 4.

И так далее до конца первого этапа.

На втором этапе начинаем со 2-го элемента (4) и повторяем те же действия, пока массив не будет отсортирован.

---

Вычислительная сложность

Вычислительная сложность - $O(n^2)$

---

Псевдокод

Функция сортировка_пузырьком(данные, количество данных)
    Для индекса числа_1 в диапазоне от 0 до количества данных - 2
        Для индекса числа_2 в диапазоне от 0 до количества данных - 2
            Если данные по индексу числа_2 больше данных по индексу числа_2 + 1
                Меняем местами данные по индексу числа_1 и данные по индексу числа_1 + 1
    Вернуть данные

---

Реализация на Python

Аннотация:
bubble_sort - функция сортировки пузырьком
A - сортируемый массив
i, j - индексы массива

def bubble_sort(A: list):
    for i in range(0, len(A) - 1):
        for j in range(0, len(A) - 1):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]
    return A

---

Олимпиадная реализация на C++

Аннотация:
bubble_sort - функция сортировки пузырьком
arr - сортируемый массив
size - размер массива
i, j - индексы массива

int* bubble_sort(int* arr, int size) {
for (int i = 0; i < size - 1; i++)
    for (int j = 0; j < size - 1; j++)
        if (arr[j] > arr[j + 1])
            std::swap(arr[j], arr[j + 1]);
}

---

Продуктовая реализация на C++

Аннотация:
comp - функция сравнения данных
first_data, second_data - сравниваемые данные 
bubble_sort - функция сортировки пузырьком
arr - сортируемый массив
size - размер массива
i, j - индексы массива

template<typename T>
bool comp(T first_data, T second_data){
    return first_data > second_data;
}

template <typename T arr>
T* bubble_sort(T *arr, int size, bool comp){
    for (int i = 0; i < size - 1; i++){
        for (int j = 0; j < size - 1; j++){
            if (comp(a[j], a[j + 1])){
                std::swap(a[j], a[j + 1]);
            }
        }
    }
}