методы поиска. ЛАБА1. Отчет по лабораторной работе 1 по дисциплине Структуры и алгоритмы обработки данных

• Название: Отчет по лабораторной работе 1 по дисциплине Структуры и алгоритмы обработки данных
• Анкор: методы поиска
• Дата: 24.11.2022
• Размер: 210.49 Kb.
• Имя файла: ЛАБА1.docx
• Тип: Отчет; #811019

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

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

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

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

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

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

(МТУСИ)

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

Отчет по лабораторной работе № 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) – Метод, генерирующий матрицу;

defselectionSort(b) – Метод сортировки выбором;

definsertionSort(b) – Метод сортировки вставкой;
defexchangeSort(b) – Метод сортировки обменом;

defshellsSort(b) – Метод сортировки Шелла;

deftournamentSort(array) – Метод турнирной сортировки;

defsupportTournamentSortMethod(arr) – Вспомогательный метод турнирной сортировки;

defquickSort(a) – Метод быстрой сортировки;

defsupportQuickSortMethod(anotherFirst, anotherLast, array, row) – Вспомогательный метод быстрой сортировки ;

defsupportPyramidSortMethod(a, n, i) – Вспомогательный метод пирамидальной сортировки;

defpyramidSort(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 и различные методы сортировки массивов. А также сравнила время работы каждого метода сортировки со встроенной.