Выбор сортировки

Решение: Selection Sort (Сортировка выбором)

Понимание алгоритма

Selection Sort работает в два этапа:

1. Найти минимальный элемент в неотсортированной части массива
2. Поменять его с первым элементом неотсортированной части
3. Сдвинуть границу отсортированной части на одну позицию

Решение 1: Классическая реализация

def selection_sort(arr: list[int]) -> list[int]:
    arr_copy = arr.copy()
    
    for i in range(len(arr_copy)):
        # Найти минимальный элемент в оставшейся части
        min_idx = i
        for j in range(i + 1, len(arr_copy)):
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
        
        # Поменять элементы местами
        arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
    
    return arr_copy

Time Complexity: O(n^2) Space Complexity: O(1) если сортировать in-place

Решение 2: In-place сортировка (оптимально)

def selection_sort_inplace(arr: list[int]) -> None:
    for i in range(len(arr)):
        # Найти индекс минимального элемента
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Поменять местами если найден меньший элемент
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

Решение 3: С подсчётом операций (для отладки)

def selection_sort_debug(arr: list[int]) -> tuple[list[int], dict]:
    arr_copy = arr.copy()
    comparisons = 0
    swaps = 0
    
    for i in range(len(arr_copy)):
        min_idx = i
        for j in range(i + 1, len(arr_copy)):
            comparisons += 1
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
        
        if min_idx != i:
            swaps += 1
            arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
    
    return arr_copy, {
        'comparisons': comparisons,
        'swaps': swaps,
        'total_operations': comparisons + swaps
    }

Примеры использования

# Базовый пример
arr = [64, 25, 12, 22, 11]
result = selection_sort(arr)
print(result)  # [11, 12, 22, 25, 64]

# In-place сортировка
arr = [5, 2, 8, 1, 9]
selection_sort_inplace(arr)
print(arr)  # [1, 2, 5, 8, 9]

# С отладкой
arr = [64, 25, 12, 22, 11]
sorted_arr, stats = selection_sort_debug(arr)
print(f"Отсортировано: {sorted_arr}")
print(f"Операций сравнения: {stats['comparisons']}")
print(f"Операций обмена: {stats['swaps']}")

Визуализация работы

Для массива [64, 25, 12, 22, 11]:

Итерация 1: Минимум = 11 [11, 25, 12, 22, 64]

Итерация 2: Минимум = 12 (из [25, 12, 22, 64]) [11, 12, 25, 22, 64]

Итерация 3: Минимум = 22 (из [25, 22, 64]) [11, 12, 22, 25, 64]

Итерация 4: Минимум = 25 (из [25, 64]) [11, 12, 22, 25, 64]

Итерация 5: Завершено

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

Граничные случаи

# Пустой массив
assert selection_sort([]) == []

# Один элемент
assert selection_sort([5]) == [5]

# Два элемента
assert selection_sort([2, 1]) == [1, 2]

# Уже отсортирован
assert selection_sort([1, 2, 3, 4]) == [1, 2, 3, 4]

# В обратном порядке
assert selection_sort([4, 3, 2, 1]) == [1, 2, 3, 4]

# Дубликаты
assert selection_sort([3, 1, 3, 1, 2]) == [1, 1, 2, 3, 3]

# Отрицательные числа
assert selection_sort([-1, -5, 3, -2, 0]) == [-5, -2, -1, 0, 3]

Преимущества Selection Sort

1. Простая реализация
2. O(1) дополнительная память
3. Стабильное количество операций O(n^2)
4. Хороша для маленьких массивов (n < 50)
5. Минимизирует число операций записи (max n-1 свопов)

Недостатки Selection Sort

1. O(n^2) временная сложность
2. Нестабильна (не сохраняет порядок равных элементов)
3. Медленнее других алгоритмов для больших данных
4. Не адаптивна (время одинаково для отсортированных и неотсортированных)

Сравнение с другими алгоритмами

Когда использовать Selection Sort:

• Когда память критична (O(1))
• Для маленьких массивов (n < 50)
• Когда нужна простая реализация
• Когда нужно минимизировать свопы

Когда использовать другие:

• Quick Sort: для больших случайных данных
• Merge Sort: когда нужна стабильность и гарантированно O(n log n)
• Insertion Sort: для почти отсортированных данных
• Tim Sort: для реальных данных (Python, Java)

Для QA автоматизации

Selection Sort демонстрирует понимание:

• Базовых алгоритмических концепций
• Временной и пространственной сложности
• Обмена переменных (swap)
• Поиска минимума в диапазоне
• In-place алгоритмов

Используйте эту реализацию для тестирования сортировки массивов в автотестах.