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

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

Алгоритм

Алгоритм сортировки пузырьком работает следующим образом:

1. Проходим по массиву, сравнивая попарно соседние элементы.
2. Если элементы находятся в неправильном порядке, меняем их местами.
3. Повторяем процесс до тех пор, пока весь массив не будет отсортирован.

Анализ сложности

• Временная сложность сортировки пузырьком: В худшем и лучшем случаях $O(n^2)$, где $n$ - количество элементов.
• Пространственная сложность сортировки пузырьком: $O(1)$, так как сортировка происходит "на месте" без использования дополнительных структур данных.

Реализация

Приведём примеры реализации сортировки пузырьком:

Python

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

C++

#include <vector>

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

Java

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Заключение

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

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