Изучение известные алгоритмы сортировок
Цель данной лабораторной работы — посмотреть на алгоритмы с различной асимптотикой, научиться анализировать время работы алгоритмов и включать разные степени оптимизации.
Сортировка пузырьком:
Алгоритм:
Берём самый первый элемент массива и сравниваем его со вторым. Если первый больше второго — меняем их местами с первым, если нет — ничего не делаем. Затем берём второй элемент массива и сравниваем его со следующим — третьим. Если второй больше третьего — меняем их местами, если нет — ничего не делаем. Проходим так до предпоследнего элемента, сравниваем его с последним и ставим наибольший из них в конец массива. Всё, мы нашли самое большое число в массиве и поставили его на своё место. Возвращаемся в начало алгоритма и делаем всё снова точно так же, начиная с первого и второго элемента. Только теперь даём себе задание не проверять последний элемент — мы знаем, что теперь в конце массива самый большой элемент. Когда закончим очередной проход — уменьшаем значение финальной позиции, до которой проверяем, и снова начинаем сначала. Так делаем до тех пор, пока у нас не останется один элемент.
Асимптотика: O (N^2)
Код сортировки с выводом графика:
import random
import time
import matplotlib
matplotlib.use('TkAgg') # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict
# Пузырьковая сортировка
def sort_array(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[j] <= arr[i]:
continue
arr[i], arr[j] = arr[j], arr[i]
# Заполнение массива случайными значениями
def fill_array(arr):
for i in range(len(arr)):
arr[i] = random.randint(-len(arr), len(arr))
# Подсчет времени выполнения функции
def running_time(action, arr):
start_time = time.time()
action(arr)
return (time.time() - start_time) * 1000 # Время в миллисекундах
def display_statistics():
results = defaultdict(int)
# Сбор результатов
for i in range(500, 5050, 50):
ar = [0] * i
fill_array(ar)
results[i] = running_time(sort_array, ar)
# Обработка данных для графика
sizes = list(results.keys())
times = list(results.values())
# Построение основного графика
plt.figure(figsize=(12, 6))
# График с обычным масштабом
plt.subplot(1, 2, 1) # 1 строка, 2 колонки, 1-й график
plt.plot(sizes, times, label='Sort Productivity', marker='o')
plt.title('Время сортировки в зависимости от размера массива')
plt.xlabel('Размер массива')
plt.ylabel('Время сортировки, мс')
plt.legend()
plt.grid()
# Построение графика с двойным логарифмическим масштабом
plt.subplot(1, 2, 2) # 1 строка, 2 колонки, 2-й график
plt.plot(sizes, times, label='Sort Productivity (log-log)', marker='o')
plt.title('Время сортировки (лог-лог масштаб)')
plt.xlabel('Размер массива (лог)')
plt.ylabel('Время сортировки (лог)')
plt.xscale('log')
plt.yscale('log')
plt.legend()
plt.grid()
plt.tight_layout() # Компактное размещение графиков
plt.show()
if __name__ == "__main__":
display_statistics()Сортировка вставкой O (N2):
Алгоритм: Проходим по массиву слева направо и обрабатываем по очереди каждый элемент. Слева от очередного элемента наращиваем отсортированную часть массива, справа по мере процесса потихоньку испаряется неотсортированная. В отсортированной части массива ищется точка вставки для очередного элемента. Сам элемент отправляется в буфер, в результате чего в массиве появляется свободная ячейка — это позволяет сдвинуть элементы и освободить точку вставки.
Асимптотика: O (N^2)
Код сортировки с выводом графика:
import random
import time
import matplotlib
matplotlib.use('TkAgg') # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict
# Сортировка вставками
def sort_array(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Заполнение массива случайными значениями
def fill_array(arr):
for i in range(len(arr)):
arr[i] = random.randint(-len(arr), len(arr))
# Подсчет времени выполнения функции
def running_time(action, arr):
start_time = time.time()
action(arr)
return (time.time() - start_time) * 1000 # Время в миллисекундах
def display_statistics():
results = defaultdict(int)
# Сбор результатов
for i in range(500, 5050, 50):
ar = [0] * i
fill_array(ar)
results[i] = running_time(sort_array, ar)
# Обработка данных для графика
sizes = list(results.keys())
times = list(results.values())
# Построение основного графика
plt.figure(figsize=(12, 6))
# График с обычным масштабом
plt.subplot(1, 2, 1) # 1 строка, 2 колонки, 1-й график
plt.plot(sizes, times, label='Sort Productivity', marker='o')
plt.title('Время сортировки в зависимости от размера массива')
plt.xlabel('Размер массива')
plt.ylabel('Время сортировки, мс')
plt.legend()
plt.grid()
# Построение графика с двойным логарифмическим масштабом
plt.subplot(1, 2, 2) # 1 строка, 2 колонки, 2-й график
plt.plot(sizes, times, label='Sort Productivity (log-log)', marker='o')
plt.title('Время сортировки (лог-лог масштаб)')
plt.xlabel('Размер массива (лог)')
plt.ylabel('Время сортировки (лог)')
plt.xscale('log')
plt.yscale('log')
plt.legend()
plt.grid()
plt.tight_layout() # Компактное размещение графиков
plt.show()
if __name__ == "__main__":
display_statistics()Сортировкой шейкером O (N2):
Алгоритм: Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.
Асимптотика: O (N^2)
Код сортировки с выводом графика:
import random
import time
import matplotlib
matplotlib.use('TkAgg') # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict
# Сортировка шейкером
def sort_array(arr):
n = len(arr)
swapped = True
start = 0
end = n - 1
while swapped:
swapped = False
# Проход вперед
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
end -= 1
if not swapped:
break
swapped = False
# Проход назад
for i in range(end, start, -1):
if arr[i] < arr[i - 1]:
arr[i], arr[i - 1] = arr[i - 1], arr[i]
swapped = True
start += 1
# Заполнение массива случайными значениями
def fill_array(arr):
for i in range(len(arr)):
arr[i] = random.randint(-len(arr), len(arr))
# Подсчет времени выполнения функции
def running_time(action, arr):
start_time = time.time()
action(arr)
return (time.time() - start_time) * 1000 # Время в миллисекундах
def display_statistics():
results = defaultdict(int)
# Сбор результатов
for i in range(500, 5050, 50):
ar = [0] * i
fill_array(ar)
results[i] = running_time(sort_array, ar)
# Обработка данных для графика
sizes = list(results.keys())
times = list(results.values())
# Построение основного графика
plt.figure(figsize=(12, 6))
# График с обычным масштабом
plt.subplot(1, 2, 1) # 1 строка, 2 колонки, 1-й график
plt.plot(sizes, times, label='Sort Productivity', marker='o')
plt.title('Время сортировки в зависимости от размера массива')
plt.xlabel('Размер массива')
plt.ylabel('Время сортировки, мс')
plt.legend()
plt.grid()
# Построение графика с двойным логарифмическим масштабом
plt.subplot(1, 2, 2) # 1 строка, 2 колонки, 2-й график
plt.plot(sizes, times, label='Sort Productivity (log-log)', marker='o')
plt.title('Время сортировки')
plt.xlabel('Размер массива (лог)')
plt.ylabel('Время сортировки (лог)')
plt.xscale('log')
plt.yscale('log')
plt.legend()
plt.grid()
plt.tight_layout() # Компактное размещение графиков
plt.show()
if __name__ == "__main__":
display_statistics()Сортировка кучей:
Алгоритм: Алгоритм пирамидальной сортировки в порядке по возрастанию:
Постройте max-heap из входных данных.
На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
Повторяйте вышеуказанные шаги, пока размер кучи больше 1.
Как построить кучу?
Процедура преобразования в кучу (далее процедура heapify) может быть применена к узлу, только если его дочерние узлы уже преобразованы. Таким образом, преобразование должно выполняться снизу вверх. Давайте разберемся с помощью примера:
Входные данные: 4, 10, 3, 5, 1
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Числа в скобках представляют индексы в представлении данных в виде массива.
Применение процедуры heapify к индексу 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Применение процедуры heapify к индексу 0:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
Процедура heapify вызывает себя рекурсивно для создания кучи сверху вниз.
Асимптотика: O (N*log (N))
Код сортировки с выводом графика:
import random
import time
import matplotlib
matplotlib.use('TkAgg') # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict
# Сортировка кучей
def heapify(arr, n, i):
largest = i # Инициализируем максимальный элемент как корень
left = 2 * i + 1 # Левый дочерний элемент
right = 2 * i + 2 # Правый дочерний элемент
# Если левый дочерний элемент больше корня
if left < n and arr[left] > arr[largest]:
largest = left
# Если правый дочерний элемент больше текущего максимума
if right < n and arr[right] > arr[largest]:
largest = right
# Если находимся не в правильной позиции, меняем местами
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Меняем местами
heapify(arr, n, largest) # Рекурсивно преобразуем подкучу в кучу
def sort_array(arr):
n = len(arr)
# Строим кучу (перегружаем по убыванию)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Один за другим извлекаем элементы из кучи
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Меняем местами
heapify(arr, i, 0)
# Заполнение массива случайными значениями
def fill_array(arr):
for i in range(len(arr)):
arr[i] = random.randint(-len(arr), len(arr))
# Подсчет времени выполнения функции
def running_time(action, arr):
start_time = time.time()
action(arr)
return (time.time() - start_time) * 1000 # Время в миллисекундах
def display_statistics():
results = defaultdict(int)
# Сбор результатов
for i in range(500, 5050, 50):
ar = [0] * i
fill_array(ar)
results[i] = running_time(sort_array, ar)
# Обработка данных для графика
sizes = list(results.keys())
times = list(results.values())
# Построение основного графика
plt.figure(figsize=(12, 6))
# График с обычным масштабом
plt.subplot(1, 2, 1) # 1 строка, 2 колонки, 1-й график
plt.plot(sizes, times, label='Sort Productivity', marker='o')
plt.title('Время сортировки в зависимости от размера массива')
plt.xlabel('Размер массива')
plt.ylabel('Время сортировки, мс')
plt.legend()
plt.grid()
# Построение графика с двойным логарифмическим масштабом
plt.subplot(1, 2, 2) # 1 строка, 2 колонки, 2-й график
plt.plot(sizes, times, label='Sort Productivity (log-log)', marker='o')
plt.title('Время сортировки ')
plt.xlabel('Размер массива (лог)')
plt.ylabel('Время сортировки (лог)')
plt.xscale('log')
plt.yscale('log')
plt.legend()
plt.grid()
plt.tight_layout() # Компактное размещение графиков
plt.show()
if __name__ == "__main__":
display_statistics()Сортировка Хоара:
На каждом шаге алгоритма сначала выбирается «средний» элемент, затем переставляются элементы массива так, что массив разделился на две части. Первая часть содержит элементы, меньше «среднего» и, возможно, равные ему. Вторая часть содержит элементы больше «среднего» и, возможно, равные ему. После такого деления массива остается только отсортировать его части по отдельности, с которыми поступаем аналогично (делим на две части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован. В случае, когда массив содержит только одинаковые элементы, выбор «среднего» элемента не производится и сортировка не осуществляется.
Разделение массива на две части производится следующим образом. Устанавливаем один курсор на левую границу массива, а второй — на правую границу. Затем осуществляем перемещение курсоров навстречу друг другу до тех пор, пока они не пересекутся. При перемещении курсоров сравниваем значения текущих элементов со «средним». Находим левый текущий элемент, больший «среднего», и правый текущий элемент, меньше «среднего» (то есть, элементы, которые находятся «не на своем месте»). Осуществляем обмен этих элементов.
Выбор «среднего» — задача непростая, так как требуется, не производя сортировку, найти элемент со значением максимально близким к среднему. Здесь, конечно, можно просто выбрать произвольный элемент (обычно выбирают элемент, стоящий в середине сортируемого подмассива), но пойдем чуть дальше: из трех элементов (самого левого, самого правого и стоящего посередине) выберем средний.
Асимптотика: O (N*log (N))
Код сортировки с выводом графика:
Зависимость от начальных данных.
Рассмотрим время каждой сортировки и оценим зависимость времени от количества элементов в массиве в лучшем, произвольном и худшем случаях.
Сортировка пузырьком:
Сортировка вставкой:
Сортировка шейкером:
Сортировка кучей:
Сортировка Хоар:
Сортировка слиянием:
Зависимость от типа данных.
Попробуем отсортировать массивы других типов данных и сравнить время работы.
Небольшие массивы.
Рассмотрим на такую неочевидную штуку, как время работы шести предыдущих сортировок на небольших массивах (примерно 1 — 1000 элементов). Суть в том, что асимптотика начинает работать при очень больших N — неспроста во всех выкладках и оценках мы отбрасывали все слагаемые, кроме тех, что указаны в самой асимптотике. А при малых N эти слагаемые и коэффициенты при них вылезают, что может сильно повлиять на итоговое время работы.
