ЗАДАНИЕ 4 Написать программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» (усовершенствованная версия задани я 2) и методом выбора. Выполнить ее тестирование на разных 10 массивах, содержащих 1000 случайных элементов, вычислить среднее число перестановок для каждого метода после тестирования.

Для решения данной задачи, мы напишем программу на Python, которая будет реализовывать два метода сортировки: "сортировка пузырьком" и "сортировка выбором", одновременно считая количество перестановок элементов. После этого будет проведено тестирование на 10 массивах, содержащих 1000 случайных элементов, и вычислено среднее число перестановок для каждого метода. ### Шаги для решения задачи: 1. **Импортируем необходимые библиотеки**: Для генерации случайных массивов мы будем использовать библиотеку `random`. 2. **Реализуем функцию для сортировки пузырьком**: Эта функция будет сортировать массив и считать количество перестановок. 3. **Реализуем функцию для сортировки выбором**: Аналогично, эта функция будет сортировать массив с подсчетом перестановок. 4. **Генерируем 10 случайных массивов** каждый из которых будет содержать 1000 элементов. 5. **Тестируем оба метода сортировки на сгенерированных массивах**, сохраняем количество перестановок и вычисляем средние значения. ### Пример кода: ```python import random # Функция сортировки пузырьком с подсчетом перестановок def bubble_sort_count_swaps(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_count_swaps(arr): n = len(arr) swap_count = 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 if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i] swap_count += 1 return swap_count # Генерация 10 случайных массивов num_arrays = 10 array_size = 1000 bubble_swaps = [] selection_swaps = [] for _ in range(num_arrays): arr = [random.randint(1, 10000) for _ in range(array_size)] # Копируем массив для сортировки "пузырьком" arr_bubble = arr.copy() swaps_bubble = bubble_sort_count_swaps(arr_bubble) bubble_swaps.append(swaps_bubble) # Копируем массив для сортировки "выбором" arr_selection = arr.copy() swaps_selection = selection_sort_count_swaps(arr_selection) selection_swaps.append(swaps_selection) # Вычисляем среднее количество перестановок average_bubble_swaps = sum(bubble_swaps) / num_arrays average_selection_swaps = sum(selection_swaps) / num_arrays # Выводим результаты print(f"Среднее количество перестановок при сортировке пузырьком: {average_bubble_swaps}") print(f"Среднее количество перестановок при сортировке выбором: {average_selection_swaps}") ``` ### Объяснение кода: 1. **Функции сортировки**: - `bubble_sort_count_swaps`: реализует сортировку пузырьком. В каждом шаге, если текущий элемент больше следующего, то они меняются местами, и счетчик `swap_count` увеличивается. - `selection_sort_count_swaps`: реализует сортировку выбором. На каждой итерации ищется минимальный элемент, и если он не на нужной позиции, происходит обмен, который также подсчитывается. 2. **Генерация массивов**: - Мы создаем 10 массивов случайных чисел (от 1 до 10000), содержащих 1000 элементов каждый. 3. **Тестирование и расчет среднего**: - Для каждого массива подсчитывается количество перестановок для двух методов сортировки, после чего средние значения выводятся на экран. Эти шаги должны помочь вам понять, как сравнить количество перестановок при использовании разных методов сортировки. Если у вас есть вопросы по коду или методам сортировки, не стесняйтесь спрашивать!