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

Сортировка пузырьком

Сортировка пузырьком - один из самых простых алгоритмов сортировки. Он работает путем сравнения соседних элементов и их перестановки, если они находятся в неправильном порядке. Процесс повторяется до тех пор, пока все элементы не будут отсортированы.

Как работает алгоритм:

1. Проходим по массиву от начала до конца.

2. Сравниваем каждый элемент с его следующим соседом.

3. Если элементы находятся в неправильном порядке, меняем их местами.

4. Повторяем шаги 1-3 до тех пор, пока в массиве не останется ни одной пары элементов, которые нужно поменять местами.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Первый проход:

• Сравниваем 5 и 1. Они в неправильном порядке, меняем их местами: [1, 5, 4, 2, 8].

• Сравниваем 5 и 4. Они в неправильном порядке, меняем их местами: [1, 4, 5, 2, 8].

• Сравниваем 5 и 2. Они в неправильном порядке, меняем их местами: [1, 4, 2, 5, 8].

• Сравниваем 5 и 8. Они в правильном порядке.

Второй проход:

• Сравниваем 1 и 4. Они в правильном порядке.

• Сравниваем 4 и 2. Они в неправильном порядке, меняем их местами: [1, 2, 4, 5, 8].

• Сравниваем 4 и 5. Они в правильном порядке.

• Сравниваем 5 и 8. Они в правильном порядке.

Третий проход:

• Сравниваем 1 и 2. Они в правильном порядке.

• Сравниваем 2 и 4. Они в правильном порядке.

• Сравниваем 4 и 5. Они в правильном порядке.

• Сравниваем 5 и 8. Они в правильном порядке.

Теперь массив отсортирован: [1, 2, 4, 5, 8].

Преимущества:

• Простой для понимания и реализации.

Недостатки:

• Медленный для больших массивов.

• Неэффективен для почти отсортированных массивов.

Сложность:

• Время: O(n^2) в худшем и среднем случае, O(n) в лучшем случае (когда массив уже отсортирован).

Использование:

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

Код сортировки с выводом графика:

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)

Сортировка вставкой - это простой алгоритм сортировки, который работает путем постепенного построения отсортированного подмассива. Он перебирает элементы исходного массива и вставляет каждый из них в правильное положение в уже отсортированном подмассиве.

Как работает алгоритм:

1. Начинаем с первого элемента, который уже является отсортированным подмассивом.

2. Перебираем оставшиеся элементы исходного массива.

3. Для каждого элемента:

   • Сравниваем его с элементами отсортированного подмассива, двигаясь справа налево, пока не найдем элемент, который меньше или равен текущему.

   • Перемещаем все элементы, большие, чем текущий, на одну позицию вправо.

   • Вставляем текущий элемент в освободившееся место.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Первый шаг:

• Подмассив отсортирован: [5]

• Вставляем 1 в подмассив: [1, 5]

Второй шаг:

• Подмассив отсортирован: [1, 5]

• Вставляем 4 в подмассив: [1, 4, 5]

Третий шаг:

• Подмассив отсортирован: [1, 4, 5]

• Вставляем 2 в подмассив: [1, 2, 4, 5]

Четвертый шаг:

• Подмассив отсортирован: [1, 2, 4, 5]

• Вставляем 8 в подмассив: [1, 2, 4, 5, 8]

Теперь массив отсортирован.

Преимущества:

• Простой для понимания и реализации.

• Эффективен для почти отсортированных массивов.

Недостатки:

• Медленный для больших массивов.

Сложность:

• Время: O(n^2) в худшем и среднем случае, O(n) в лучшем случае (когда массив уже отсортирован).

Использование:

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

Код сортировки с выводом графика:

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)

Сортировка шейкером (англ. Cocktail sort) - это вариант алгоритма сортировки пузырьком, который оптимизирован для более быстрого достижения результата. Вместо того чтобы просто проходить по массиву от начала до конца, сортировка шейкером перемещается взад и вперед, как коктейльный шейкер.

Как работает алгоритм:

1. Проход вперед: Сравниваем каждый элемент с его соседом справа, как в сортировке пузырьком. Меняем элементы местами, если они в неправильном порядке.

2. Проход назад: Сравниваем каждый элемент с его соседом слева, также меняя элементы местами при необходимости.

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

4. Повторение: Повторяем шаги 1-3, но с каждым проходом уменьшаем диапазон сортировки, ограничивая его только неотсортированными частями массива, которые были затронуты в предыдущих проходах.

5. Остановка: Процесс повторяется до тех пор, пока весь массив не будет отсортирован.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Первый проход (вперед):

• [1, 5, 4, 2, 8]

• [1, 4, 5, 2, 8]

• [1, 4, 2, 5, 8]

• [1, 4, 2, 5, 8]

Первый проход (назад):

• [1, 2, 4, 5, 8]

Второй проход (вперед):

• [1, 2, 4, 5, 8] (ничего не меняется)

Второй проход (назад):

• [1, 2, 4, 5, 8] (ничего не меняется)

Массив отсортирован.

Преимущества:

• Более быстрый, чем сортировка пузырьком.

Недостатки:

• Не такой эффективный, как некоторые другие алгоритмы сортировки, такие как сортировка слиянием или сортировка кучей.

Сложность:

• Время: O(n^2) в худшем и среднем случае, O(n) в лучшем случае.

Использование:

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

Код сортировки с выводом графика:

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()

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

Сортировка кучей (англ. Heap sort) - это алгоритм сортировки, основанный на структуре данных кучи. Он работает путем построения кучи из исходного массива, а затем извлечения элементов из кучи по одному в порядке убывания.

Как работает алгоритм:

1. Построение кучи: Преобразуем исходный массив в бинарную кучу (обычно в виде максимальной кучи, где родительский узел всегда больше, чем его дочерние узлы).

2. Извлечение элементов: Повторяем следующие шаги, пока куча не опустеет:

   • Меняем местами корневой элемент (наибольший) с последним элементом в куче.

   • Уменьшаем размер кучи на один.

   • Восстанавливаем свойство кучи для нового корневого элемента, просеивая его вниз по дереву.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Построение кучи:

1. Начинаем с последнего узла, имеющего потомков (индекс 2, значение 4) и просеиваем его вниз.

2. Продолжаем просеивать вниз все узлы, имеющие потомков, пока не достигнем корня.

Извлечение элементов:

1. Меняем местами корневой элемент (8) с последним элементом (2).

2. Уменьшаем размер кучи.

3. Восстанавливаем свойство кучи, просеивая вниз новый корневой элемент (2).

4. Повторяем шаги 1-3, пока куча не опустеет.

Преимущества:

• Достаточно эффективный алгоритм сортировки.

• Имеет хорошую временную сложность в худшем случае.

Недостатки:

• Может быть сложнее для понимания и реализации, чем некоторые другие алгоритмы сортировки.

Сложность:

• Время: 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()

Сортировка Хоара

Сортировка Хоара, также известная как быстрая сортировка, - это алгоритм сортировки с рекурсивным подходом. Она разделяет массив на два подмассива, один с элементами, меньшими чем опорный элемент, а другой - с элементами, большими чем опорный элемент. Затем алгоритм рекурсивно сортирует эти подмассивы.

Как работает алгоритм:

1. Выбор опорного элемента: Выбирается случайный элемент из массива.

2. Разбиение: Массив перестраивается таким образом, что все элементы, меньшие опорного элемента, находятся слева от него, а все элементы, большие опорного элемента, находятся справа от него.

3. Рекурсия: Алгоритм рекурсивно применяется к двум подмассивам, пока весь массив не будет отсортирован.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Первый шаг:

• Выбираем опорный элемент, например, 5.

• Разделяем массив: [1, 2, 4, 5, 8]

• Теперь все элементы, меньшие 5, находятся слева, а все элементы, большие 5, находятся справа.

Второй шаг:

• Рекурсивно сортируем левую часть: [1, 2, 4]

• Рекурсивно сортируем правую часть: [8]

Третий шаг:

• Рекурсивно сортируем [1, 2, 4], получая [1, 2, 4].

• [8] уже отсортирован.

Четвертый шаг:

• Объединяем отсортированные подмассивы: [1, 2, 4, 5, 8]

Теперь массив отсортирован.

Преимущества:

• Быстрый алгоритм сортировки (особенно для больших массивов).

• Эффективен для сортировки массивов с различными типами данных.

Недостатки:

• Неэффективен для уже отсортированных массивов.

• Не является устойчивым (может нарушать порядок одинаковых элементов).

• Требует дополнительной памяти для рекурсии.

Сложность:

• Время: O(n log n) в среднем случае, O(n^2) в худшем случае.

Использование:

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

Код сортировки с выводом графика:

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()

Сортировка слиянием.

Сортировка слиянием (англ. Merge sort) - это алгоритм сортировки, который работает путем рекурсивного разбиения массива на два подмассива, сортировки этих подмассивов и затем слияния их обратно в один отсортированный массив.

Как работает алгоритм:

1. Разделение: Массив рекурсивно делится на два подмассива до тех пор, пока каждый подмассив не будет содержать только один элемент (один элемент уже считается отсортированным).

2. Слияние: Отсортированные подмассивы сливаются попарно, создавая новые отсортированные подмассивы большего размера.

3. Повторение: Шаги 1 и 2 повторяются, пока не останется только один отсортированный массив, который будет являться результатом сортировки.

Пример:

Пусть у нас есть массив чисел: [5, 1, 4, 2, 8]

Разделение:

1. [5, 1, 4, 2, 8] -> [5, 1, 4] и [2, 8]

2. [5, 1, 4] -> [5, 1] и [4]

3. [5, 1] -> [5] и [1]

4. [2, 8] -> [2] и [8]

Слияние:

1. [5] и [1] сливаются в [1, 5]

2. [4] остается [4]

3. [1, 5] и [4] сливаются в [1, 4, 5]

4. [2] и [8] сливаются в [2, 8]

5. [1, 4, 5] и [2, 8] сливаются в [1, 2, 4, 5, 8]

Теперь массив отсортирован.

реимущества:

• Эффективный алгоритм сортировки (особенно для больших массивов).

• Устойчивый (сохраняет порядок одинаковых элементов).

• Имеет хорошую временную сложность в худшем случае.

Недостатки:

• Требует дополнительной памяти для хранения временных массивов.

• Может быть менее эффективным для небольших массивов.

Сложность:

• Время: O(n log n) в худшем, среднем и лучшем случае.

Использование:

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

Код сортировки с выводом графика:

import random
import time
import matplotlib
matplotlib.use('TkAgg')  # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict

# Сортировка слиянием
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2  # Находим середину массива
    left_half = merge_sort(arr[:mid])  # Рекурсивно сортируем левую половину
    right_half = merge_sort(arr[mid:])  # Рекурсивно сортируем правую половину

    # Слияние отсортированных половин
    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0

    # Слияние элементов двух массивов
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # Добавление оставшихся элементов (если есть)
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    return sorted_array

# Подсчет времени выполнения функции
def running_time(action, arr):
    start_time = time.time()
    action(arr)
    return (time.time() - start_time) * 1000  # Время в миллисекундах

# Заполнение массива случайными значениями
def fill_array(arr):
    for i in range(len(arr)):
        arr[i] = random.randint(-len(arr), len(arr))

def display_statistics():
    results = defaultdict(int)

    # Сбор результатов
    for i in range(500, 5050, 50):
        ar = [0] * i
        fill_array(ar)
        results[i] = running_time(lambda x: merge_sort(x), 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()

Зависимость от начальных данных

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

• Лучший случай: Уже отсортированный массив. Сложность - O(n), так как алгоритм выполняет один проход по массиву, не меняя ничего.

• Средний случай: Случайный массив. Сложность - O(n^2).

• Худший случай: Отсортированный в обратном порядке массив. Сложность - O(n^2), так как алгоритм должен сравнивать и менять местами элементы для каждой пары.

2. Сортировка вставкой:

• Лучший случай: Уже отсортированный массив. Сложность - O(n), так как алгоритм выполняет один проход по массиву, не меняя ничего.

• Средний случай: Случайный массив. Сложность - O(n^2).

• Худший случай: Отсортированный в обратном порядке массив. Сложность - O(n^2).

3. Сортировка шейкером:

• Лучший случай: Уже отсортированный массив. Сложность - O(n), так как алгоритм выполняет один проход по массиву, не меняя ничего.

• Средний случай: Случайный массив. Сложность - O(n^2), но обычно быстрее, чем сортировка пузырьком.

• Худший случай: Отсортированный в обратном порядке массив. Сложность - O(n^2).

4. Сортировка кучей:

• Лучший случай: Любой массив. Сложность - O(n log n).

• Средний случай: Любой массив. Сложность - O(n log n).

• Худший случай: Любой массив. Сложность - O(n log n).

5. Сортировка Хоара (Быстрая сортировка):

• Лучший случай: Случайный массив. Сложность - O(n log n).

• Средний случай: Случайный массив. Сложность - O(n log n).

• Худший случай: Уже отсортированный массив или отсортированный в обратном порядке массив. Сложность - O(n^2).

6. Сортировка слиянием:

• Лучший случай: Любой массив. Сложность - O(n log n).

• Средний случай: Любой массив. Сложность - O(n log n).

• Худший случай: Любой массив. Сложность - O(n log n).

Выводы:

• Сортировка пузырьком, вставкой и шейкером сильно зависят от начальных данных. Их производительность в худшем случае - O(n^2).

• Сортировка кучей, Хоара (быстрая сортировка) и слиянием имеют временную сложность O(n log n) в худшем случае, что делает их более эффективными для большинства случаев.

• Сортировка кучей является наиболее стабильной и не зависит от начальных данных.

Важно отметить:

• Не все алгоритмы одинаково эффективны для всех типов массивов.

• Важно понимать, как различные алгоритмы сортировки ведут себя в разных ситуациях.

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

Сортировка пузырьком:

Сортировка вставкой:

Сортировка шейкером:

Сортировка кучей:

Сортировка Хоар:

Сортировка слиянием:

Зависимость от типа данных

Алгоритмы сортировки, которые мы рассматривали, в основном работают с числовыми данными, но могут быть применены и к другим типам данных, с некоторыми модификациями или ограничениями:

1. Сортировка пузырьком, вставкой, шейкером:

• Числа: Работают хорошо для целых чисел, действительных чисел, дробных чисел и т.д.

• Строки: Могут использоваться для сортировки строк по алфавиту, но могут быть менее эффективны из-за необходимости сравнения строк посимвольно.

• Объекты: Требуют определения способа сравнения объектов (например, по определенному атрибуту).

2. Сортировка кучей:

• Числа: Работает хорошо для всех типов чисел.

• Строки: Требует определения способа сравнения строк.

• Объекты: Требует определения способа сравнения объектов.

3. Сортировка Хоара (Быстрая сортировка):

• Числа: Работает хорошо для всех типов чисел.

• Строки: Требует определения способа сравнения строк.

• Объекты: Требует определения способа сравнения объектов.

4. Сортировка слиянием:

• Числа: Работает хорошо для всех типов чисел.

• Строки: Требует определения способа сравнения строк.

• Объекты: Требует определения способа сравнения объектов.

Дополнительные замечания:

• Сравнение: Большинство алгоритмов сортировки основаны на сравнении элементов. Необходимо определить способ сравнения элементов разных типов данных (например, по алфавиту для строк, по значению атрибута для объектов).

• Устойчивость: Некоторые алгоритмы сортировки (например, сортировка слиянием) являются устойчивыми, то есть они сохраняют порядок одинаковых элементов. Другие алгоритмы (например, сортировка Хоара) не являются устойчивыми.

• Дополнительная память: Сортировка слиянием требует дополнительной памяти для хранения временных массивов.

• Эффективность: Не все алгоритмы сортировки одинаково эффективны для всех типов данных. Например, сортировка пузырьком может быть менее эффективной для сортировки строк, чем для сортировки чисел.

Вывод:

Выбор алгоритма сортировки зависит от типа данных, который нужно отсортировать, и от требований к производительности.

• Числа: Большинство алгоритмов работают эффективно для чисел.

• Строки и объекты: Для строк и объектов нужно определить способ сравнения.

• Устойчивость: Если порядок одинаковых элементов должен быть сохранен, то следует использовать устойчивый алгоритм (например, сортировка слиянием).

Важно определить способ сравнения элементов для каждого типа данных, чтобы алгоритм сортировки мог правильно упорядочить элементы.

Код для вывода данного графика (график на примере сортировки шейкера):

import random
import time
import matplotlib.pyplot as plt
from collections import defaultdict

# Шейкерная сортировка (Cocktail Sort)
def shaker_sort(arr):
    left = 0
    right = len(arr) - 1
    swapped = True

    while swapped:
        swapped = False
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        right -= 1

        if not swapped:
            break

        swapped = False
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        left += 1

# Функция для заполнения массива случайными значениями
def fill_array_random(arr, data_type):
    if data_type == 'int':
        for i in range(len(arr)):
            arr[i] = random.randint(0, 1000)  # Случайные числа от 0 до 1000
    elif data_type == 'char':
        for i in range(len(arr)):
            arr[i] = chr(random.randint(97, 122))  # маленькие буквы a-z
    elif data_type == 'long int':
        for i in range(len(arr)):
            arr[i] = random.randint(0, 10000000)  # Случайные длинные целые числа
    elif data_type == 'short int':
        for i in range(len(arr)):
            arr[i] = random.randint(0, 32767)  # диапазон для short int

# Измерение времени
def running_time(action, arr):
    start_time = time.time()
    action(arr)  # Вызов функции сортировки
    return (time.time() - start_time) * 1000  # Время в миллисекундах

# Функция для отображения статистики
def display_statistics():
    types = ['int', 'char', 'long int', 'short int']
    sizes = [1000, 2000, 3000, 4000, 5000, 7000, 9000, 10000]  # Увеличенное количество размеров массивов

    plt.figure(figsize=(12, 8))  # Подготовка фигуры

    for data_type in types:
        results = defaultdict(list)  # Храним результаты для графика

        for size in sizes:
            arr = [0] * size  # Создаем массив необходимого размера
            fill_array_random(arr, data_type)  # Заполняем массив случайными значениями

            # Измеряем время сортировки
            time_taken = running_time(shaker_sort, arr)
            results[size] = time_taken

        # Подготовка данных для графика
        sizes = list(results.keys())
        times = list(results.values())

        # Создание графика
        plt.plot(sizes, times, label=f'Sorting Time for {data_type}', marker='o')

    # Настройка графика
    plt.title('Sorting Time Comparison for Different Data Types')
    plt.xlabel('Array Size')
    plt.ylabel('Sorting Time (ms)')
    plt.grid()
    plt.legend()
    plt.show()

if __name__ == "__main__":
    display_statistics()

Небольшие массивы

Время работы алгоритмов сортировки в значительной степени зависит от размера массива.

Маленькие массивы:

• Сортировка пузырьком, вставкой, шейкером: Эти алгоритмы имеют временную сложность O(n^2) в худшем случае. Для маленьких массивов, где n невелико, их время работы может быть вполне приемлемым, так как квадратичная зависимость не очень сильно сказывается.

• Сортировка кучей, Хоара (быстрая сортировка), слиянием: Эти алгоритмы имеют временную сложность O(n log n) в худшем случае. Для маленьких массивов, где n невелико, log n невелико, и время работы может быть даже быстрее, чем у O(n^2) алгоритмов.

Пример:

• Сортировка пузырьком: Для массива из 5 элементов может потребоваться 10 операций сравнения и обмена, что довольно быстро.

• Сортировка слиянием: Для массива из 5 элементов также потребуются некоторые операции для разделения и слияния, но они все равно будут выполнены быстро.

Важно отметить:

• Overhead: Некоторые алгоритмы сортировки, такие как сортировка слиянием, имеют больший overhead (дополнительные операции), связанные с их реализацией. Для маленьких массивов overhead может занимать значительную часть времени работы алгоритма, делая их менее эффективными, чем O(n^2) алгоритмы.

• Преждевременная оптимизация: Не стоит тратить время на оптимизацию алгоритма для маленьких массивов, если это не является критическим фактором для производительности приложения.

Рекомендации:

• Маленькие массивы: В большинстве случаев O(n^2) алгоритмы, такие как сортировка вставкой, являются хорошим выбором для маленьких массивов.

• Большие массивы: Для больших массивов O(n log n) алгоритмы, такие как сортировка слиянием, более эффективны, так как они более устойчивы к квадратичной зависимости от размера массива.

Дополнительные факторы:

• Cache: Доступ к данным в памяти кэша происходит значительно быстрее, чем к данным, хранящимся на диске. Алгоритмы, которые лучше используют кэш (например, сортировка вставкой), могут работать быстрее для маленьких массивов.

• Специфика данных: Тип данных (числа, строки, объекты) также может влиять на производительность алгоритмов сортировки, как описано в предыдущем разделе.

Вывод:

Для маленьких массивов, размер которых меньше 10-20 элементов, разница в производительности между алгоритмами сортировки O(n^2) и O(n log n) не так критична. Выбор алгоритма может основываться на простоте реализации, устойчивости или других специфических требованиях. Для больших массивов O(n log n) алгоритмы более эффективны, так как они более устойчивы к квадратичной зависимости от размера массива.

Код для вывода данного графика:

import random
import time
import matplotlib
matplotlib.use('TkAgg')  # Используйте соответствующий бэкенд
import matplotlib.pyplot as plt
from collections import defaultdict

# Сортировка Хоара (Quicksort)
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # Случайный опорный элемент
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Сортировка пузырьком
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Шейкерная сортировка
def shaker_sort(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        right -= 1
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
        left += 1

# Сортировка вставками
def insertion_sort(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 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 heap_sort(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 merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# Подсчет времени выполнения функции
def running_time(action, arr):
    start_time = time.time()
    action(arr)
    return (time.time() - start_time) * 1000  # Время в миллисекундах

# Заполнение массива случайными значениями
def fill_array(size):
    return [random.randint(-size, size) for _ in range(size)]

def display_statistics():
    algorithms = {
        "Quicksort": lambda x: quicksort(x.copy()),
        "Bubble Sort": lambda x: bubble_sort(x.copy()),
        "Shaker Sort": lambda x: shaker_sort(x.copy()),
        "Insertion Sort": lambda x: insertion_sort(x.copy()),
        "Heap Sort": lambda x: heap_sort(x.copy()),
        "Merge Sort": lambda x: merge_sort(x.copy())
    }

    results = defaultdict(lambda: defaultdict(list))

    # Сбор результатов только для размеров <= 1000
    for size in range(500, 1001, 50):  # Изменил диапазон для размера до 1000
        arr = fill_array(size)
        for algo_name, algo in algorithms.items():
            time_taken = running_time(algo, arr)
            results[algo_name][size] = time_taken

    # Построение графиков
    plt.figure(figsize=(12, 6))

    for algo_name, algo_results in results.items():
        sizes = list(algo_results.keys())
        times = list(algo_results.values())
        plt.plot(sizes, times, label=algo_name)

    plt.title('Время сортировки в зависимости от размера массива')
    plt.xlabel('Размер массива')
    plt.ylabel('Время сортировки, мс')
    plt.legend()
    plt.grid()
    plt.yscale("log")  # Логарифмическое масштабирование по оси Y
    plt.show()

if __name__ == "__main__":
    display_statistics()