PrepBro
← Назад к вопросам

Сортировка пузырьком

2.0 Middle🔥 171 комментариев
#Теория тестирования

Условие

Реализуйте алгоритм сортировки пузырьком для массива целых чисел. Не используйте встроенные методы сортировки.

Пример

Вход: [64, 34, 25, 12, 22, 11, 90] Выход: [11, 12, 22, 25, 34, 64, 90]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Сортировка пузырьком

Описание задачи

Требуется реализовать алгоритм сортировки пузырьком (bubble sort) для массива целых чисел без использования встроенных методов сортировки. Сортировка пузырьком — это классический алгоритм сортировки, который многократно проходит по массиву, сравнивает соседние элементы и обменивает их местами, если они находятся в неправильном порядке. Хотя в реальной практике этот алгоритм считается неэффективным (O(n²)), он является отличным инструментом обучения и часто встречается в тестировании алгоритмов, обучении программированию и интервью.

Решение на Python

def bubble_sort(arr):
    """
    Реализует сортировку пузырьком.
    
    Args:
        arr: список целых чисел
    
    Returns:
        отсортированный список
    """
    n = len(arr)
    arr_copy = arr.copy()  # Работаем с копией, не изменяем исходный массив
    
    # Проходим по всему массиву
    for i in range(n):
        # Флаг для оптимизации: если обменов не было, массив отсортирован
        swapped = False
        
        # Проходим по оставшейся части массива
        for j in range(0, n - i - 1):
            # Если текущий элемент больше следующего
            if arr_copy[j] > arr_copy[j + 1]:
                # Обмениваем их местами
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
                swapped = True
        
        # Если обменов не было, массив уже отсортирован
        if not swapped:
            break
    
    return arr_copy

Альтернативные подходы

1. Базовая сортировка пузырьком (без оптимизации)

def bubble_sort_basic(arr):
    """
    Самый простой вариант без оптимизаций.
    Всегда выполняет O(n²) сравнений.
    """
    n = len(arr)
    arr_copy = arr.copy()
    
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr_copy[j] > arr_copy[j + 1]:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
    
    return arr_copy

2. Сортировка пузырьком с изменением исходного массива

def bubble_sort_inplace(arr):
    """
    Модифицирует исходный массив напрямую.
    Экономит память, но изменяет входные данные.
    """
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:
            break
    
    return arr

3. Сортировка с детальным логированием

def bubble_sort_verbose(arr, debug=False):
    """
    Сортировка пузырьком с логированием итераций.
    Полезна для обучения и отладки.
    """
    n = len(arr)
    arr_copy = arr.copy()
    comparisons = 0
    swaps = 0
    
    for i in range(n):
        swapped = False
        
        if debug:
            print(f'Проход {i + 1}: {arr_copy}')
        
        for j in range(0, n - i - 1):
            comparisons += 1
            
            if arr_copy[j] > arr_copy[j + 1]:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
                swaps += 1
                
                if debug:
                    print(f'  Обмен: {arr_copy[j+1]} и {arr_copy[j]}')
        
        if not swapped:
            break
    
    if debug:
        print(f'Всего сравнений: {comparisons}, обменов: {swaps}')
    
    return arr_copy

4. Сортировка пузырьком с поддержкой компаратора

def bubble_sort_custom(arr, key=None, reverse=False):
    """
    Сортировка пузырьком с поддержкой пользовательского ключа сортировки.
    """
    n = len(arr)
    arr_copy = arr.copy()
    
    for i in range(n):
        swapped = False
        
        for j in range(0, n - i - 1):
            val1 = key(arr_copy[j]) if key else arr_copy[j]
            val2 = key(arr_copy[j + 1]) if key else arr_copy[j + 1]
            
            # Сравнение в зависимости от direction
            should_swap = (val1 > val2) if not reverse else (val1 < val2)
            
            if should_swap:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
                swapped = True
        
        if not swapped:
            break
    
    return arr_copy

Тестовые примеры

import unittest

class TestBubbleSort(unittest.TestCase):
    
    def test_basic_case(self):
        # Базовый случай из условия
        input_arr = [64, 34, 25, 12, 22, 11, 90]
        expected = [11, 12, 22, 25, 34, 64, 90]
        assert bubble_sort(input_arr) == expected
    
    def test_empty_array(self):
        # Пустой массив
        assert bubble_sort([]) == []
    
    def test_single_element(self):
        # Один элемент
        assert bubble_sort([42]) == [42]
    
    def test_two_elements(self):
        # Два элемента
        assert bubble_sort([2, 1]) == [1, 2]
    
    def test_already_sorted(self):
        # Уже отсортированный массив
        assert bubble_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]
    
    def test_reverse_sorted(self):
        # Обратно отсортированный массив (худший случай)
        assert bubble_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    
    def test_duplicates(self):
        # С дубликатами
        assert bubble_sort([3, 1, 2, 1, 3]) == [1, 1, 2, 3, 3]
    
    def test_negative_numbers(self):
        # С отрицательными числами
        assert bubble_sort([3, -1, 4, -2, 0]) == [-2, -1, 0, 3, 4]
    
    def test_large_array(self):
        # Большой массив
        input_arr = list(range(100, 0, -1))
        expected = list(range(1, 101))
        assert bubble_sort(input_arr) == expected
    
    def test_all_same(self):
        # Все элементы одинаковые
        assert bubble_sort([5, 5, 5, 5, 5]) == [5, 5, 5, 5, 5]
    
    def test_original_not_modified(self):
        # Исходный массив не должен быть изменён
        original = [3, 1, 2]
        result = bubble_sort(original)
        assert original == [3, 1, 2]  # Исходный не изменился
        assert result == [1, 2, 3]    # Результат правильный

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

АспектЗначениеПримечание
Временная сложность (худший)O(n²)Обратно отсортированный массив
Временная сложность (лучший)O(n)Уже отсортированный массив
Временная сложность (средний)O(n²)Случайный порядок
Пространственная сложностьO(1) или O(n)В зависимости от in-place варианта
СтабильностьДаРавные элементы остаются в исходном порядке
Сравнения≈ n²/2В среднем
ОбменыЗависит от порядкаОт 0 до n²/2

Применение в QA Automation

  • Функциональное тестирование — проверка корректности реализации алгоритма сортировки
  • Performance тестирование — сравнение времени выполнения на массивах разного размера
  • Граничные случаи — пустые массивы, один элемент, дубликаты
  • Мемори-тестирование — проверка использования памяти
  • Обучение — демонстрация концепций алгоритмов и оптимизаций
  • Регрессионное тестирование — убедиться, что сортировка работает после изменений

Оптимизации в коде

  1. Флаг swapped — прерывает цикл, если массив уже отсортирован (лучший случай O(n))
  2. Сокращение диапазона — n - i - 1 исключает уже отсортированные элементы
  3. Копирование — не модифицируем исходный массив (в основном варианте)

Рекомендация

Для стандартного использования в QA рекомендуется основной вариант с флагом swapped — он хорошо демонстрирует алгоритм и включает оптимизацию. В реальной практике используйте встроенную сортировку (.sort() или sorted()), так как она оптимизирована и намного быстрее. Сортировка пузырьком полезна в основном для обучения и алгоритмических интервью.