Федеральное агентство связи

Ордена Трудового Красного Знамени

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский технический университет связи и информатики»

Кафедра Математической Кибернетики и Информационных Технологий

Отчет по лабораторной работе

по предмету «СиАОД»

на тему:

«Методы сортировки»

Выполнил: студент группы УБСТ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.