Напишите программу на Python для сравнения количества перестановок элементов при использовании сортировки пузырьком

Конечно, вот программа на Python для сравнения количества перестановок элементов при использовании сортировки пузырьком, метода выбора и быстрой сортировки:

python

import random

import time



def bubble_sort(arr):

    n = len(arr)

    swaps = 0

    for i in range(n - 1):

        for j in range(0, n - i - 1):

            if arr[j] > arr[j + 1]:

                arr[j], arr[j + 1] = arr[j + 1], arr[j]

                swaps += 1

    return swaps



def selection_sort(arr):

    n = len(arr)

    swaps = 0

    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):

            if arr[j] < arr[min_idx]:

                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

        swaps += 1

    return swaps



def quick_sort(arr):

    if len(arr) <= 1:

        return 0

    

    pivot = arr[0]

    lesser = [x for x in arr[1:] if x <= pivot]

    greater = [x for x in arr[1:] if x > pivot]

    

    return quick_sort(lesser) + quick_sort(greater) + len(lesser)



def test_sorting_methods():

    num_arrays = 10

    array_size = 1000

    

    bubble_swaps = 0

    selection_swaps = 0

    quick_swaps = 0

    

    for _ in range(num_arrays):

        arr = [random.randint(1, 1000) for _ in range(array_size)]

        

        bubble_swaps += bubble_sort(arr.copy())

        selection_swaps += selection_sort(arr.copy())

        quick_swaps += quick_sort(arr.copy())

    

    avg_bubble_swaps = bubble_swaps / num_arrays

    avg_selection_swaps = selection_swaps / num_arrays

    avg_quick_swaps = quick_swaps / num_arrays

    

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

    print(f"Среднее количество перестановок для сортировки выбором: {avg_selection_swaps}")

    print(f"Среднее количество перестановок для быстрой сортировки: {avg_quick_swaps}")



# Тестирование

test_sorting_methods()

Обоснование:

1. Для сравнения количества перестановок используются три различных алгоритма сортировки: сортировка пузырьком, сортировка выбором и быстрая сортировка.
2. Каждый алгоритм работает с копиями исходного массива, чтобы сохранить одинаковые начальные условия для сравнения.
3. В функции `bubble_sort` используется двойной цикл for для сравнения и перестановки элементов. Каждый раз, когда происходит перестановка, увеличивается счетчик `swaps`.
4. В функции `selection_sort` используется цикл for для поиска минимального элемента в неотсортированной части массива и его обмена с первым элементом этой части. Каждый раз, когда происходит обмен, увеличивается счетчик `swaps`.
5. В функции `quick_sort` используется алгоритм быстрой сортировки с рекурсивным подходом. Разделяются подмассивы, меньшие и большие опорного элемента, и рекурсивно сортируются. Количество перестановок равно сумме количества перестановок в меньших и больших подмассивах, а также количества элементов в меньших подмассивах.
6. Функция `test_sorting_methods` проводит несколько тестовых запусков каждого алгоритма на случайно сгенерированных массивах, состоящих из 1000 элементов. Суммарное количество перестановок каждого алгоритма вычисляется и делится на количество тестовых запусков, чтобы получить среднее количество перестановок.
7. Наконец, программа выводит среднее количество перестановок для каждого метода сортировки.

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