Министерство цифрового развития и массовых коммуникаций
Российской Федерации
Ордена Трудового Красного Знамени федеральное государственное
бюджетное образовательное учреждение
высшего образования
«Московский технический университет связи и информатики»
(МТУСИ)
Кафедра Математическая кибернетика и информационные технологии
Отчет по лабораторной работе № 1
по дисциплине «Структуры и алгоритмы обработки данных»
на тему: «Методы сортировки»
Вариант 11
Выполнила: студентка группы БСТ20
Проверил: Чайка А.Д.
Москва 2022
1 Цель работы
Изучить основы синтаксиса Python. Изучить различные методы сортировки массивов.
2 Задание
Посредством создания нового python-проекта произвести решение следующих задания:
Задание №1
Создать программу, которая выводит в консоль фразу «Hello, world!».
Задание №2
Написать генератор случайных матриц(многомерных), который принимает опциональные параметры m, n, min_limit, max_limit, где m и n указывают размер матрицы, а min_lim и max_lim - минимальное и максимальное значение для генерируемого числа . По умолчанию при отсутствии параметров принимать следующие значения: m = 50, n = 50, min_limit = -250, max_limit = 1011.
Задание №3
Реализовать методы сортировки строк числовой матрицы в соответствии с заданием. Оценить время работы каждого алгоритма сортировки и сравнить его со временем стандартной функции сортировки. Испытания проводить на сгенерированных матрицах.
Методы: Выбором, вставкой, обменом, Шелла, турнирная, быстрая, пирамидальная.
Задание №4
Создать публичный репозиторий на github, и запушить выполненное задание.
3 Ход работы
3.1. Ход работы над заданием №1
3.1.1 Код программы
print("Hello, world!")
3.1.2 Результат работы программы
Рисунок 1 – Результат работы первой программы
3.2. Ход работы над заданием №2
3.2.1 Код программы
import random s = input() M = [50, 50, -250, 1011] if (s != ''): i = 0 j = 0 while i < len(s): s_int = '' flag = False while '0' <= s[i] <= '9' or s[i] == '-': if s[i] == '-': flag = True else: s_int += s[i] i += 1 if i >= len(s): break i += 1 M[j] = int(s_int) if flag: M[j] *= -1 j += 1 Matrix = [[random.randint(M[2], M[3]) for i in range(M[0])] for i in range(M[1])] for i in range(M[1]): for j in range(M[0]): print(Matrix[i][j], end = ' ') print()
3.2.2 Результат работы программы
Рисунок 2 – Результат работы второй программы
3.3. Ход работы над заданием №3
3.3.1 Описание программы
def generateArray(m = 50, n = 50, min_limit = 250, max_limit = 1011) – Метод, генерирующий матрицу;
def selectionSort(b) – Метод сортировки выбором;
def insertionSort(b) – Метод сортировки вставкой; def exchangeSort(b) – Метод сортировки обменом;
def shellsSort(b) – Метод сортировки Шелла;
def tournamentSort(array) – Метод турнирной сортировки;
def supportTournamentSortMethod(arr) – Вспомогательный метод турнирной сортировки;
def quickSort(a) – Метод быстрой сортировки;
def supportQuickSortMethod(anotherFirst, anotherLast, array, row) – Вспомогательный метод быстрой сортировки ;
def supportPyramidSortMethod(a, n, i) – Вспомогательный метод пирамидальной сортировки;
def pyramidSort(b) – Метод пирамидальной сортировки.