1 практика

2

1 Введение

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

3

2Ход работы

2.1Сортировка расческой

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

На рисунке 2.1 представлен результат работы программы.

Рисунок 2.1 – Сортировка расческой

В приложении А представлен листинг программы сортировки расческой.

2.2Быстрая сортировка

Быстрая сортировка вставками – этот алгоритм сегментирует элементы на отсортированные и неотсортированные начиная со второго элемента. Алгоритм перебирает все элементы второго сегмента и вставляет их в первый сегмент на свою позицию.

На рисунке 2.2 представлен результат работы программы.

4

Рисунок 2.2 – Быстрая сортировка

В приложении Б представлен листинг программы быстрой сортировки.

2.3Сортировка методом Шелла

Сортировка методом Шелла - алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.

На рисунке 2.3 представлена блок схема алгоритма сортировки методом Шелла.

5

Рисунок 2.3 – Блок схема сортировки методом Шелла.

На рисунке 2.4 представлен результат работы программы.

6

Рисунок 2.4 – Сортировка методом Шелла

В приложении В представлен листинг программы сортировки методом Шелла.

7

3 Алгоритмическая сложность

Сортировка выбором для массива из n элементов имеет время выполнения в худшем, среднем и лучшем случае O(n2), предполагая, что сравнения делаются за постоянное время.

При использовании метода сортировки расчёской сложность алгоритма равняется O(n*log2n).

А сортировка методом Шелла имеет такую же сложность, как и пузырьковая сортировка, то есть O(n2).

8

Заключение

В ходе выполнения практической работы были разработаны программы для быстрой сортировки, сортировки методом Шелла и сортировки растёской.

Все задания выполнены на языке программирования Python.

Наиболее затруднительным был создание собственных функция для алгоритмов сортировки.

Отчет был составлен согласно ОС ТУСУР 2021.

9

Приложение А

(обязательное)

Сортировка расческой

import random mas = []

a = 100000 count = 0

b = int(input())

for l in range(0,100000): count+=1

x1 = random.randint(1,a) mas.append(x1)

if count==b: break

def comb(m):

step = int(len(m)/1.247) swap = 1

while step > 1 or swap > 0: swap = 0

i = 0

while i + step < len(m): if m[i] > m[i+step]:

m[i], m[i+step] = m[i+step], m[i] swap += 1

i += 1 if step > 1:

step = int(step / 1.247)

comb(mas) print(mas)

10