Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных…

Чтобы понять, как сравнить число перестановок элементов при использовании различных сортировок, давайте рассмотрим три алгоритма сортировки: сортировку «пузырьком», метод выбора и быструю сортировку. Мы реализуем каждый из алгоритмов и подсчитаем количество перестановок, произошедших в ходе сортировки. Затем протестируем все три метода на 1000 случайных числах и вычислим среднее количество перестановок для каждого метода.

Вот шаги, которые мы будем выполнять, и код для решения задачи:

Шаг 1: Импортируем библиотеки

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

Шаг 2: Реализуем алгоритмы сортировки

Каждый алгоритм сортировки будет включать счетчик для подсчета перестановок.

Шаг 3: Генерация массива

Сгенерируем массив на 1000 случайных чисел.

Шаг 4: Сравнение

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

Вот пример программы:

import random

# Функция для сортировки пузырьком
def bubble_sort(arr):
    n = len(arr)
    swap_count = 0
    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]
                swap_count += 1
    return swap_count

# Функция для сортировки методом выбора
def selection_sort(arr):
    n = len(arr)
    swap_count = 0
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
            swap_count += 1
    return swap_count

# Функция для быстрой сортировки
def quicksort(arr):
    if len(arr) <= 1:
        return arr, 0
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    left_sorted, left_swaps = quicksort(left)
    right_sorted, right_swaps = quicksort(right)
    return left_sorted + middle + right_sorted, left_swaps + right_swaps + len(left) + len(right) - 1

# Функция для вычисления среднего кол-ва перестановок
def average_swaps(sort_function, iterations=10):
    total_swaps = 0
    for _ in range(iterations):
        arr = [random.randint(0, 1000) for _ in range(1000)]  # Генерация массива
        if sort_function == quicksort:
            _, swaps = quicksort(arr.copy())
        else:
            swaps = sort_function(arr.copy())
        total_swaps += swaps
    return total_swaps / iterations

# Сравнение количества перестановок
bubble_avg = average_swaps(bubble_sort)
selection_avg = average_swaps(selection_sort)
quicksort_avg = average_swaps(quicksort)

print(f"Среднее количество перестановок для сортировки пузырьком: {bubble_avg}")
print(f"Среднее количество перестановок для сортировки методом выбора: {selection_avg}")
print(f"Среднее количество перестановок для быстрой сортировки: {quicksort_avg}")

Объяснение кода:

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

2. Функция selection_sort: Реализует сортировку методом выбора и также считает перестановки, только когда происходит замена.

3. Функция quicksort: Имплементация быстрой сортировки, где перестановки не считаются напрямую. Вместо этого, общий счет производится на уровне рекурсии.

4. Функция average_swaps: Запускает заданный метод сортировки несколько раз, вычисляя среднее количество перестановок.

5. Основная часть программы: Вычисляет среднее количество перестановок для всех трех алгоритмов и выводит результаты.

Заключение

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