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

Сергей_6390

3

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

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

python

import random

2. Затем создайте функцию "пузырьковой сортировки", которая будет принимать массив чисел и возвращать отсортированный массив, а также количество перестановок. Добавьте следующий код:

python

def bubble_sort(arr):

    n = len(arr)

    swaps = 0

    for i in range(n-1):

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

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

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

                swaps += 1

    return arr, swaps

3. Затем определите функцию "сортировки выбором", которая также будет принимать массив чисел и возвращать отсортированный массив и количество перестановок. Добавьте этот код:

python

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 arr, swaps

4. Наконец, создайте функцию "быстрой сортировки", которая будет использовать рекурсивный алгоритм быстрой сортировки. Эта функция также будет принимать массив чисел и возвращать отсортированный массив и количество перестановок. Вот код:

python

def quick_sort(arr):

    if len(arr) <= 1:

        return arr, 0

    pivot = arr[len(arr)//2]

    left = [x for x in arr if x < pivot]

    equal = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    sorted_left, swaps_left = quick_sort(left)

    sorted_right, swaps_right = quick_sort(right)

    sorted_arr = sorted_left + equal + sorted_right

    total_swaps = swaps_left + swaps_right + len(equal)

    return sorted_arr, total_swaps

5. Теперь вам нужно создать массив случайных чисел и протестировать все три алгоритма сортировки на этом массиве. Добавьте следующий код:

python

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



bubble_sorted_arr, bubble_swaps = bubble_sort(arr)

selection_sorted_arr, selection_swaps = selection_sort(arr)

quick_sorted_arr, quick_swaps = quick_sort(arr)



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

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

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

Этот код сначала создает массив arr, состоящий из 1000 случайных чисел от 1 до 1000. Затем он применяет каждый алгоритм сортировки и выводит количество перестановок для каждого из них.

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

Надеюсь, это поможет вам понять, как решить данную задачу! Если у вас возникнут дополнительные вопросы, не стесняйтесь задавать. Удачи в изучении программирования!