Файл: Практическая работа 3 оценка эффективности алгоритмов часть Алгоритмы сортировки.pdf

1
ПРАКТИЧЕСКАЯ РАБОТА № 3
ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ
Часть 1. Алгоритмы сортировки
Цель работы – научиться оценивать временную и пространственную сложность алгоритмов, познакомиться с различными алгоритмами сортировки, сравнить их эффективность по памяти и количеству операций.
Постановка задачи
Провести сравнение указанных алгоритмов сортировки массивов, содержащих N1, N2, N3 и
N4 элементов.
Работа выполняется в три этапа.
На первом этапе нужно произвести теоретические расчеты трудоемкости по заданному критерию в нотациях О и Ω, а также оценить пространственную сложность алгоритма в нотации
О.
На втором этапе нужно провести эксперимент, для чего написать программу, в которой для каждого алгоритма сортировки выполнить по отдельности подсчет основных (производимых над элементами массива) и вспомогательных (всех остальных) операций, указанных в вариативной части задания (сравнений или присваиваний), вычислить количество используемой алгоритмом дополнительной памяти, а также зафиксировать время работы алгоритма. Каждую функцию сортировки вызывать трижды: для сортировки неупорядоченного массива, упорядоченного массива и массива, упорядоченного в обратном порядке. Сортируемая последовательность для всех методов должна быть одинаковой (считывать необходимое количество элементов из прилагаемого файла test_numbers.txt).
На третьем, заключительном, этапе нужно произвести анализ полученных теоретических и практических результатов, сравнить алгоритмы по вычислительной и пространственной сложности и выбрать из анализируемых наиболее эффективный алгоритм.
При выполнении задания на повышенном уровне сложности дополнительно провести анализ того, как наличие повторяющихся ключей во входной последовательности влияет на трудоемкость каждого из рассматриваемых алгоритмов сортировки. При выполнении практической части задания для этого нужно создать четыре файла, содержащих N4 неупорядоченных чисел, в которых значения элементов будут повторяться по 10, 100, 500 и 1000 раз, и так же, как в первой половине работы, выполнить сортировку этих последовательностей (неупорядоченных, упорядоченных и упорядоченных в обратном порядке) каждым из методов.

2
Варианты заданий
Вариант № 1
Порядок: по убыванию элементов. Методы: выбора, пузырька, пирамидальная сортировка, быстрая сортировка. N1=5000, N2=30000, N3=100000, N4=120000. Критерий – количество сравнений.
Вариант № 2
Порядок: по возрастанию элементов. Методы: выбора, пузырька, пирамидальная сортировка, быстрая сортировка. N1=10000, N2=30000, N3=70000, N4=100000. Критерий – количество присваиваний.
Вариант № 3
Порядок: по возрастанию элементов. Методы: пирамидальная сортировка, быстрая сортировка, сортировка прямым слиянием, Timsort. N1=50000, N2=100000, N3=150000,
N4=200 000. Критерий – количество сравнений.
Вариант № 4
Порядок: по возрастанию элементов. Методы: пузырька, шейкера, быстрая сортировка, сортировка естественным слиянием. N1=10000, N2=50000, N3=100000, N4=150000. Критерий – количество сравнений.
Вариант № 5
Порядок: по возрастанию элементов. Методы: пузырька, шейкера, быстрая сортировка, сортировка естественным слиянием. N1=20000, N2=50000, N3=80000, N4=110000. Критерий – количество присваиваний.
Вариант № 6
Порядок: по возрастанию элементов. Методы: пирамидальная сортировка, быстрая сортировка, сортировка прямым слиянием, Timsort. N1=50000, N2=100000, N3=150000,
N4=200 000. Критерий – количество присваиваний.
Вариант № 7
Порядок: по убыванию элементов. Методы: пузырька, пузырька с фиксацией места обмена, шейкера, быстрая сортировка. N1=10000, N2=18000, N3=30000, N4=60000. Критерий – количество сравнений.
Вариант № 8
Порядок: по убыванию элементов. Методы: выбора, простых вставок, Шелла (шаг сортировки h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1
), пирамидальная сортировка. N1=50000, N2=90000,
N3=120000, N4=1500 00. Критерий – количество присваиваний.
Вариант № 9
Порядок: по возрастанию элементов. Методы: быстрая сортировка, сортировка прямым

3 слиянием, сортировка естественным слиянием, Timsort. N1=60000, N2=90000, N3=120000,
N4=150 000. Критерий – количество сравнений.
Вариант № 10
Порядок: по убыванию элементов. Методы: простых вставок, бинарных вставок, Шелла
(шаг сортировки h
k-1
=3h
k
+1, h
t
=1, t=log
3
n-
1 и h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1). N1=10000, N2=30000,
N3=70000, N4=10000 0. Критерий – количество сравнений.
Вариант № 11
Порядок: по возрастанию элементов. Методы: пирамидальная сортировка, метод Хоара, сортировка прямым слиянием, сортировка естественным слиянием. N1=5000, N2=100000,
N3=150000, N4=200 000. Критерий – количество сравнений.
Вариант № 12
Порядок: по возрастанию элементов. Методы: простых вставок, Шелла (шаг сортировки
h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1
), сортировка естественным слиянием, Timsort. N1=10000, N2=30000,
N3=70000, N4=100 000. Критерий – количество присваиваний.
Вариант № 13
Порядок: по возрастанию элементов. Методы: быстрая сортировка, сортировка прямым слиянием, сортировка естественным слиянием, поразрядная сортировка. N1=10000, N2=60000,
N3=110000, N4=16 0000. Критерий – количество присваиваний.
Вариант № 14
Порядок: по возрастанию элементов. Методы: пирамидальная сортировка, метод Хоара, сортировка прямым слиянием, сортировка естественным слиянием. N1=50000, N2=90000,
N3=120000, N4=15000 0. Критерий – количество присваиваний.
Вариант № 15
Порядок: по возрастанию элементов. Методы: простых вставок, Шелла (шаг сортировки
h
k-1
=3h
k
+1, h
t
=1, t=log
3
n-1
), сортировка естественным слиянием, Timsort. N1=20000, N2=40000,
N3=80000, N4=120 000. Критерий – количество присваиваний.
Вариант № 16
Порядок: по убыванию элементов. Методы: выбора, простых вставок, Шелла (шаг сортировки h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1)
, пирамидальная сортировка. N1=15000, N2=40000,
N3=80000, N4=120 000. Критерий – количество сравнений.
Вариант № 17
Порядок: по убыванию элементов. Методы: выбора, простых вставок, Шелла (шаг сортировки h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1
), пирамидальная сортировка. N1=10000, N2=30000,
N3=70000, N4=100 000. Критерий – количество присваиваний.
Вариант № 18

4
Порядок: по возрастанию элементов. Методы: Хоара, Timsort, сортировка прямым слиянием, поразрядная сортировка. N1=70000, N2=110000, N3=150000, N4=190000. Критерий – количество присваиваний.
Вариант № 19
Порядок: по убыванию элементов. Методы: пузырька, пузырька с фиксацией факта обмена, пузырька с фиксацией места обмена, шейкера. N1=5000, N2=15000, N3=30000, N4=50000.
Критерий – количество сравнений.
Вариант № 20
Порядок: по убыванию элементов. Методы: простых вставок, бинарных вставок, Шелла
(
шаг сортировки h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1
), Шелла (шаг сортировки задается числами
Фибоначчи). N1=5000, N2=15000, N3=45000, N4=135000. Критерий – количество присваиваний.
Вариант № 21
Порядок: по возрастанию элементов. Методы: пузырька с фиксацией места обмена, шейкера, расчески, быстрая сортировка. N1=10000, N2=30000, N3=70000, N4=100000. Критерий – количество присваиваний.
Вариант № 22
Порядок: по возрастанию элементов. Методы: выбора, простых вставок, Шелла (шаг сортировки h
k-1
=3h
k
+1, h
t
=1, t=log
3
n-1
), сортировка прямым слиянием. N1=10000, N2=18000,
N3=30000, N4=6 0000. Критерий – количество сравнений.
Вариант № 23
Порядок: по возрастанию элементов. Методы: шейкера, Шелла (шаг сортировки h
k-
1
=3h
k
+1, h
t
=1, t=log
3
n-1
), сортировка прямым слиянием, поразрядная сортировка. N1=10000,
N2=50000, N3=100000, N
4=150000. Критерий – количество присваиваний.
Вариант № 24
Порядок: по убыванию элементов. Методы: пузырька, пузырька с фиксацией места обмена, шейкера, расчески. N1=10000, N2=30000, N3=60000, N4=90000. Критерий – количество сравнений.
Вариант № 25
Порядок: по возрастанию элементов. Методы: пузырька, Шелла (шаг сортировки h
k-
1
=2h
k
+1, h
t
=1, t=log
2
n-1
), Шелла (шаг сортировки задается числами Фибоначчи), поразрядная сортировка. N1=10000, N2=30000, N3=70000, N4=100000. Критерий – количество присваиваний.
Вариант № 26
Порядок: по возрастанию элементов. Методы: бинарных вставок, Шелла (шаг сортировки
h
k-1
=3h
k
+1, h
t
=1, t=log
3
n-
1 и h
k-1
=2h
k
+1, h
t
=1, t=log
2
n-1)
, сортировка естественным слиянием.
N1=15000, N2=40000, N3=80000, N4=150 000. Критерий – количество сравнений.

5
Вариант № 27
Порядок: по убыванию элементов. Методы: пузырька с фиксацией места обмена, шейкера, расчески, быстрая сортировка. N1=15000, N2=45000, N3=75000, N4=110000. Критерий – количество сравнений.
Вариант № 28
Порядок: по возрастанию элементов. Методы: выбора, пузырька с фиксацией места обмена, бинарных вставок, поразрядная. N1=10000, N2=30000, N3=50000, N4=90000. Критерий – количество присваиваний.
Вариант № 29
Порядок: по возрастанию элементов. Методы: шейкера, сортировка прямым слиянием, сортировка естественным слиянием, поразрядная сортировка. N1=50000, N2=90000, N3=120000,
N
4=150000. Критерий – количество присваиваний.
Вариант № 30
Порядок: по возрастанию элементов. Методы: выбора, расчески, простых вставок,
Timsort. N1=30000, N2=60000, N3=90000, N4=120 000. Критерий – количество присваиваний.
Контрольные вопросы
1.
Что такое сортировка?
2.
Какие виды сортировки Вы знаете?
3.
Какие методы сортировки называются устойчивыми?
4.
Какое среднее количество сравнений требуется для прямых и улучшенных методов сортировки?
5.
На какие категории можно разбить прямые методы сортировки?
6.
Опишите алгоритм сортировки методом пузырька
7.
Опишите алгоритм сортировки методом пузырька с фиксацией факта обмена
8.
Опишите алгоритм сортировки методом пузырька с фиксацией места обмена
9.
Опишите алгоритм шейкерной сортировки
10.
Опишите алгоритм сортировки расческой
11.
Опишите алгоритм сортировки методом простых вставок
12.
Опишите алгоритм сортировки методом бинарных вставок
13.
Опишите алгоритм сортировки методом Шелла
14.
Опишите алгоритм сортировки методом прямого выбора
15.
Опишите алгоритм сортировки с помощью пирамиды
16.
Опишите алгоритм сортировки Хоара
17.
Опишите алгоритм поразрядной сортировки
18.
Опишите алгоритм сортировки Timsort

6 19.
Опишите алгоритм сортировки методом прямого слияния
20.
Опишите алгоритм сортировки методом естественного слияния
21.
Опишите алгоритм сортировки методом многопутевого слияния
22.
Опишите алгоритм многофазной сортировки
23.
Какие алгоритмы сортировки применимы для упорядочения односвязного линейного списка?
24.
Какие алгоритмы сортировки применимы для упорядочения двусвязного линейного списка?
25.
Какие особенности требуется учитывать при сортировке файлов?
26.
Какие методы сортировки файлов Вы знаете?
27.
Какой метод сортировки обычно используется для подготовки серий перед сортировкой файлов и почему выбран именно он?