Методическая разработка «Python. Сортировка»

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ДОПОЛНИТЕЛЬНОГО ОБРАЗОВАНИЯ

«ЦЕНТР ДЕТСКОГО ТЕХНИЧЕСКОГО ТВОРЧЕСТВА»

Методическая разработка

к дополнительной общеобразовательной

общеразвивающей программе

технической направленности

«Лаборатория робототехники»

Возраст детей: 10-17 лет

Автор: Костычев Вадим Александрович

г. Заречный Пензенской области

2023 г.

В ходе изучения программирования на основе языка Python большую роль играет разработка проектов. Они позволяют отработать как навыки программирования, вспомнить работу различных функций, команд, развить навыки построения алгоритмов.

Целью данной разработки является повышение интереса учащихся к техническому творчеству посредством работы над проектом на языке Python.

Данная методическая разработка используется как обучающий пример для работы по дополнительной общеобразовательной общеразвивающей программе технической направленности «Лаборатория робототехники». С их помощью учащиеся смогут применить теоретические знания на практике, построив сложные алгоритмы для решения различных задач.

Для решения различных задач в программировании применяется сортировка. Она позволяет выстроить значения по порядку от наименьшего к наибольшему или наоборот.

Существуют разные методы сортировки, среди них такие как пузырьковая сортировка, сортировка выбором, сортировка простыми вставками, сортировка Шелла, быстрая сортировка, сортировка слиянием, пирамидальная сортировка, сортировка TimSort.

Пример пузырьковой сортировки:

a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6, 8, -2, 99]

n = len(a)

for i in range(n - 1):

for j in range(n - i - 1):

if a[j] a[j + 1]: # если порядок элементов пары неправильный

a[j], a[j + 1] = a[j + 1], a[j] # меняем элементы пары местами

print('Отсортированный список:', a)

Задача 1. Сортировка пузырьком.

Программе дается список целых чисел. Оптимизируйте приведенный код, реализующий алгоритм пузырьковой сортировки.

Список a = [17, 24, 91, 96, 67, -27, 79, -71, -71, 58, 48, 88, 88, -16, -78, 96, -76, 56, 92, 1, 32, -17, 36, 88, -61]

Входные данные:

Выходные данные:

[-78, -76, -71, -71, -61, -27, -17, -16, 1, 17, 24, 32, 36, 48, 56, 58, 67, 79, 88, 88, 88, 91, 92, 96, 96]

Листинг программы:

a = [17, 24, 91, 96, 67, -27, 79, -71, -71, 58, 48, 88, 88, -16, -78, 96, -76, 56, 92, 1, 32, -17, 36, 88, -61]

n = len(a)

for i in range(n - 1):

for j in range(n - i - 1):

if a[j] a[j + 1]:

a[j], a[j + 1] = a[j + 1], a[j]

print(a)

Задача 2. Сортировка выбором

Программе дается список целых чисел. Отсортируйте список по возрастанию, реализовав алгоритм сортировки выбором.

Входные данные:

Выходные данные:

[-78, -76, -71, -71, -61, -27, -17, -16, 1, 17, 24, 32, 36, 48, 56, 58, 67, 79, 88, 88, 88, 91, 92, 96, 96]

Листинг программы:

a = [17, 24, 91, 96, 67, -27, 79, -71, -71, 58, 48, 88, 88, -16, -78, 96, -76, 56, 92, 1, 32, -17, 36, 88, -61]

n = len(a)

for i in range(n-1):

mx = max(a[:n-i])

mxi = a.index(mx)

a[n - i - 1], a[mxi] = a[mxi], a[n - i - 1]

print(a)

Задача 3. Сортировка вставками

Программе дается список целых чисел. Отсортируйте список по возрастанию, реализовав алгоритм сортировки вставками.

Входные данные:

Выходные данные:

[-78, -76, -71, -71, -61, -27, -17, -16, 1, 17, 24, 32, 36, 48, 56, 58, 67, 79, 88, 88, 88, 91, 92, 96, 96]

Листинг программы:

array = [17, 24, 91, 96, 67, -27, 79, -71, -71, 58, 48, 88, 88, -16, -78, 96, -76, 56, 92, 1, 32, -17, 36, 88, -61]

for i in range(1, len(array)):

key = array[i]

j = i-1

while array[j] key and j = 0:

array[j+1] = array[j]

j -= 1

array[j+1] = key

print(array)

Задача 4. Сортировка Шелла

Программе дается список целых чисел. Отсортируйте список по возрастанию, реализовав алгоритм сортировки Шелла.

Входные данные:

Выходные данные:

[-78, -76, -71, -71, -61, -27, -17, -16, 1, 17, 24, 32, 36, 48, 56, 58, 67, 79, 88, 88, 88, 91, 92, 96, 96]

Листинг программы:

import math

array = [17, 24, 91, 96, 67, -27, 79, -71, -71, 58, 48, 88, 88, -16, -78, 96, -76, 56, 92, 1, 32, -17, 36, 88, -61]

n = len(array)

k = int(math.log2(n))

interval = 2**k -1

while interval 0:

for i in range(interval, n):

temp = array[i]

j = i

while j = interval and array[j - interval] temp:

array[j] = array[j - interval]

j -= interval

array[j] = temp

k -= 1

interval = 2**k -1

print(array)

Задача 5. Пирамидальная сортировка

Программе дается список целых чисел. Отсортируйте список по возрастанию, реализовав алгоритм пирамидальной сортировки.

Входные данные:

Выходные данные:

[-78, -76, -71, -71, -61, -27, -17, -16, 1, 17, 24, 32, 36, 48, 56, 58, 67, 79, 88, 88, 88, 91, 92, 96, 96]

Листинг программы:

def heapify(array, n, i):

largest = i

l = 2 * i + 1

r = 2 * i + 2

if l

largest = l

if r

largest = r

if largest != i:

array[i], array[largest] = array[largest], array[i]

heapify(array, n, largest)

def heapSort(array):

n = len(array)

for i in range(n//2, -1, -1):

heapify(array, n, i)

for i in range(n-1, 0, -1):

array[i], array[0] = array[0], array[i]

heapify(array, i, 0)

return array