Сортировка пузырьком: простой, но эффективный алгоритм

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

Приведем пример кода на языке Python, который демонстрирует реализацию этого алгоритма:

python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # последние i элементов уже отсортированы, их не нужно рассматривать
        for j in range(n - i - 1):
            # сравниваем соседние элементы и меняем их местами при необходимости
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

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

Такой алгоритм имеет квадратичную сложность времени выполнения, то есть время работы увеличивается квадратично с увеличением размера входных данных. Это значит, что при больших объемах данных сортировка пузырьком может быть неэффективной и заметно замедлить работу программы.

Для более оптимальной сортировки можно использовать, например, алгоритм быстрой сортировки (quicksort) или сортировку слиянием (mergesort), которые имеют более лучшую асимптотическую сложность.