Министерство цифрового развития и массовых коммуникаций

Российской Федерации

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

бюджетное образовательное учреждение

высшего образования

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

(МТУСИ)

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

Отчет по лабораторной работе № 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) – Метод пирамидальной сортировки.

3.3.2 Код программы

import random import timeit def generateArray(m = 50, n = 50, min_limit = 250, max_limit = 1011): matrix = [[random.randint(min_limit, max_limit) for i in range(m)] for i in range(n)] for i in range(m): for j in range(n): print(matrix[j][i], end = ' ') print() return matrix def selectionSort(b): a = b.copy() for k in range(len(a)): for i in range(len(a[k]) - 1): m = i j = i + 1 while j < len(a[k]): if a[k][j] < a[k][m]: m = j j = j + 1 a[k][i], a[k][m] = a[k][m], a[k][i] return a def insertionSort(b): a = b.copy() for p in range(len(a)): for i in range(1, len(a[p])): k = a[p][i] j = i-1 while j >= 0 and k < a[p][j]: a[p][j+1] = a[p][j] j -= 1 a[p][j+1] = k return a def exchangeSort(b): a = b.copy() for p in range(len(a)): for i in range(len(a[p])): for j in range(len(a[p]) - i - 1): if a[p][j] > a[p][j + 1]: a[p][j], a[p][j + 1] = a[p][j + 1], a[p][j] return a def shellsSort(b): a = b.copy() for p in range(len(a)): d = len(a) // 2 while d: for i, el in enumerate(a[p]): while i >= d and a[p][i - d] > el: a[p][i] = a[p][i - d] i -= d a[p][i] = el d = 1 if d == 2 else int(d * 5.0 / 11) return a def tournamentSort(array): arr = array.copy() for i in range(len(arr)): supportTournamentSortMethod(arr[i]) return arr def supportTournamentSortMethod(arr): t = [None] * 2 * (len(arr) + len(arr) % 2) index = len(t) - len(arr) - len(arr) % 2 for i, v in enumerate(arr): t[index + i] = (i, v) for j in range(len(arr)): n = len(arr) index = len(t) - len(arr) - len(arr) % 2 while index > -1: n = (n + 1) // 2 for i in range(n): i = max(index + i * 2, 1) if t[i] != None and t[i + 1] != None: if t[i][1] < t[i + 1][1]: t[i // 2] = t[i] else: t[i // 2] = t[i + 1] else: t[i // 2] = t[i] if t[i] != None else t[i + 1] index -= n index, x = t[0] arr[j] = x t[len(t) - len(arr) - len(arr) % 2 + index] = None def quickSort(a): b = a.copy() for i in range(len(b)): supportQuickSortMethod(0, len(b[i]) - 1, b, i) return b def supportQuickSortMethod(anotherFirst, anotherLast, array, row): first = int(anotherFirst) last = int(anotherLast) middle = int((first + last) / 2) while (first < last): while (array[row][first] < array[row][middle]): first += 1 while (array[row][last] > array[row][middle]): last -= 1 if (first <= last): array[row][first], array[row][last] = array[row][last], array[row][first] first += 1 last -= 1 if (anotherFirst < last): supportQuickSortMethod(anotherFirst, last, array, row) if (first < anotherLast): supportQuickSortMethod(first, anotherLast, array, row) def supportPyramidSortMethod(a, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and a[i] < a[l]: largest = l if r < n and a[largest] < a[r]: largest = r if largest != i: a[i], a[largest] = a[largest], a[i] supportPyramidSortMethod(a, n, largest) def pyramidSort(b): a = b.copy() for i in range(len(a)): n = len(a[i]) for j in range(n, -1, -1): supportPyramidSortMethod(a[i], n, j) for j in range(n-1, 0, -1): a[i][j], a[i][0] = a[i][0], a[i][j] supportPyramidSortMethod(a[i], j, 0) return a s = input() if (s != ''): M = [0, 0, 0, 0] 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 arrayExample = generateArray(M[0], M[1], M[2], M[3]) else: arrayExample = generateArray() startTime = timeit.default_timer() selectionSort(arrayExample) print("Время работы сортировки выбором: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() insertionSort(arrayExample) print("Время работы сортировки вставкой: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() exchangeSort(arrayExample) print("Время работы сортировки обменом: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() shellsSort(arrayExample) print("Время работы сортировки Шелла: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() tournamentSort(arrayExample) print("Время работы турнирной сортировки: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() pyramidSort(arrayExample) print("Время работы сортировки пирамидальной сортировка: " + str(timeit.default_timer() - startTime)) startTime = timeit.default_timer() quickSort(arrayExample) print("Время работы быстрой сортировки: " + str(timeit.default_timer() - startTime)) mas = arrayExample.copy() startTime = timeit.default_timer() mas.sort() print("Время работы встроенной сортировки: " + str(timeit.default_timer() - startTime))

3.3.2 Результат работы программы

Рисунок 3 – Результат работы третьей программы при вводе дополнительных данных

Рисунок 4 – Результат работы третьей программы без ввода данных

3.2. Ход работы над заданием №4

3.2.1 Ссылка не репозиторий

https://github.com/ajuga-reptans/KuriloBST2001/tree/master/pythonProject1

3.2.2 Результат работы

Рисунок 5 – Файлы программ, загруженные в репозиторий

4 Вывод

В процессе выполнения данной лабораторной работы я изучила основы синтаксиса Python и различные методы сортировки массивов. А также сравнила время работы каждого метода сортировки со встроенной.