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

Тема урока: Сравнение сортировок в Python

Разъяснение:
Для решения данной задачи по сравнению трех сортировок - сортировки пузырьком, метода выбора и быстрой сортировки, необходимо написать программу, которая будет реализовывать каждый из этих алгоритмов сортировки и подсчитывать количество перестановок элементов в каждом случае.

1. Для сортировки пузырьком можно использовать следующий алгоритм:
- Проходить по всем элементам списка, начиная с индекса 0.
- Сравнивать каждую пару соседних элементов и, если порядок неверный, менять их местами.
- Повторять проходы по списку до тех пор, пока не будет выполнено ни одной перестановки.

2. Для метода выбора:
- Проходить по всем элементам списка, начиная с индекса 0.
- Находить наименьший элемент в оставшейся части списка и менять его местами с текущим элементом.

3. Для быстрой сортировки:
- Выбрать опорный элемент из списка.
- Разделить список на две части: элементы, меньшие опорного, и элементы, большие опорного.
- Рекурсивно применить быструю сортировку к каждой из этих частей.

Например:

python

import random



def bubble_sort(arr):

    # Реализация сортировки пузырьком

    n = len(arr)

    swaps = 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]

                swaps += 1

    return swaps



def selection_sort(arr):

    # Реализация сортировки выбором

    n = len(arr)

    swaps = 0

    for i in range(n-1):

        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):

    # Реализация быстрой сортировки

    def partition(arr, low, high):

        i = low - 1

        pivot = arr[high]

        for j in range(low, high):

            if arr[j] < pivot:

                i += 1

                arr[i], arr[j] = arr[j], arr[i]

        arr[i+1], arr[high] = arr[high], arr[i+1]

        return i+1



    def quick_sort_util(arr, low, high):

        if low < high:

            pivot = partition(arr, low, high)

            quick_sort_util(arr, low, pivot-1)

            quick_sort_util(arr, pivot+1, high)



    swaps = 0

    quick_sort_util(arr, 0, len(arr)-1)

    return swaps



# Создание случайного массива из 1000 элементов

random_arr = [random.randint(0, 1000) for _ in range(1000)]



bubble_sort_swaps = bubble_sort(random_arr.copy())

selection_sort_swaps = selection_sort(random_arr.copy())

quick_sort_swaps = quick_sort(random_arr.copy())



# Вывод среднего количества перестановок для каждого метода

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

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

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

Совет:
Для лучшего понимания алгоритмов сортировки, рекомендуется ознакомиться с теорией за основу, на которой они строятся. Также рекомендуется помнить, что все три алгоритма имеют разное время выполнения и эффективность в различных сценариях.

Задача для проверки:
Какой из трех методов сортировки - сортировка пузырьком, метод выбора или быстрая сортировка - обладает наилучшей эффективностью в данной задаче?