ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.03.2024
Просмотров: 38
Скачиваний: 0
Федеральное агентство связи
Ордена Трудового Красного Знамени
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра Математической Кибернетики и Информационных Технологий
Отчет по лабораторной работе
по предмету «СиАОД»
на тему:
«Методы сортировки»
Выполнил: студент группы УБСТ2204
Становов Роман Андреевич
Руководитель:
Кутейников Иван Алексеевич
Москва 2023
Цель работы
Реализовать заданный метод сортировки числовой матрицы в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию быстрой сортировки (quicksort). Оценить время работы каждого алгоритма сортировки и сравнить его со временем стандартной функции сортировки, используемой в выбранном языке программирования.
Вариант 19
Турнирная сортировка
Ход работы
В соответствии с заданием, реализовали алгоритм быстрой сортировки на языке Python:
# Быстрая сортировка
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[random.randint(0, len(arr) - 1)]
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
Реализовали турнирный алгоритм сортировки:
def tournament_sort(arr):
def tournament(arr):
n = len(arr)
if n == 1:
return arr[0]
winners = []
for i in range(0, n, 2):
if i == n - 1:
winners.append(arr[i])
else:
winners.append(min(arr[i], arr[i + 1]))
return tournament(winners)
Код программы
import random
import timeit
# Генерация случайного массива
def generate_random_array(size):
return [random.randint(1, 1000) for _ in range(size)]
# Турнирный метод сортировки
def tournament_sort(arr):
def tournament(arr):
n = len(arr)
if n == 1:
return arr[0]
winners = []
for i in range(0, n, 2):
if i == n - 1:
winners.append(arr[i])
else:
winners.append(min(arr[i], arr[i + 1]))
return tournament(winners)
sorted_array = []
while arr:
min_element = tournament(arr)
sorted_array.append(min_element)
arr.remove(min_element)
return sorted_array
# Быстрая сортировка
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[random.randint(0, len(arr) - 1)]
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
# Сравнение времени выполнения
array_size = 1000 # Пример размера массива
# Генерация случайного массива
array = generate_random_array(array_size)
# Время работы турнирной сортировки
tournament_sort_time = timeit.timeit(lambda: tournament_sort(array.copy()), number=100)
# Время работы быстрой сортировки
quick_sort_time = timeit.timeit(lambda: quick_sort(array.copy()), number=100)
# Время работы встроенной функции сортировки
python_sort_time = timeit.timeit(lambda: sorted(array.copy()), number=100)
print(f"Время работы турнирной сортировки: {tournament_sort_time:.6f} секунд")
print(f"Время работы быстрой сортировки: {quick_sort_time:.6f} секунд")
print(f"Время работы встроенной функции сортировки: {python_sort_time:.6f} секунд")
Вывод
При размере массива в 1 тысячу случайных чисел от 1 до 1000, лидировал встроенный метод Python.