Формальный анализ эффективности и оптимизация алгоритмов сортировки и поиска в массивах

Введение: Актуальность, Цель и Структура Исследования

В эпоху экспоненциального роста объемов данных (Big Data) и высокой производительности вычислений, эффективность алгоритмических решений перестает быть вопросом академического интереса и становится критически важным фактором конкурентоспособности. Операции сортировки и поиска являются фундаментом большинства современных информационных систем: от баз данных и операционных систем до поисковых машин и искусственного интеллекта. Неоптимальный выбор алгоритма или структуры данных может привести к катастрофическому замедлению системы при масштабировании входных данных, поэтому глубокое понимание сложности становится обязательным требованием для разработки высокопроизводительного ПО.

Актуальность исследования обусловлена необходимостью глубокого понимания не только классических алгоритмических подходов, но и современных индустриальных оптимизаций, таких как гибридные алгоритмы (Introsort, TimSort). Теоретическое знание асимптотической сложности должно быть дополнено эмпирическим анализом, позволяющим точно определить «точки переключения» (crossover points) между различными методами.

Цель работы — провести исчерпывающий теоретический анализ, математическую оценку временной и пространственной сложности ключевых алгоритмов сортировки и поиска, а также реализовать и эмпирически сравнить их эффективность на различных наборах входных данных.

Для достижения цели были поставлены следующие задачи:

1. Дать строгие определения основным понятиям теории алгоритмов и формально описать математический аппарат асимптотического анализа (O, Ω, Θ-нотации).
2. Детально разобрать механику и провести сравнительный анализ QuickSort и ShellSort, оценив их характеристики в лучшем, среднем и худшем случаях.
3. Проанализировать современные гибридные алгоритмы (Introsort, TimSort) и их оптимизационные механизмы.
4. Исследовать альтернативные структуры данных (хеш-таблицы, сбалансированные деревья) как средства повышения эффективности поиска.
5. Разработать методологию и провести эмпирическое тестирование выбранных алгоритмов на различных типах входных данных, сопоставив полученные результаты с теоретическими моделями.

Глава 1. Теоретические основы анализа алгоритмов и структур данных

Базовая терминология и свойства алгоритмов

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

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

Массив — базовая структура данных, представляющая собой упорядоченный набор элементов, расположенных в смежных ячейках памяти. Фундаментальное свойство массива, определяющее эффективность операций, заключается в возможности обращения к любому элементу по его индексу за константное время $O(1)$.

Сортировка — процесс упорядочивания множества объектов (элементов массива) по значению определенного ключа сортировки (по возрастанию или убыванию).

Ключевыми метриками оценки эффективности алгоритмов являются временная и пространственная сложность.

1. Временная сложность — характеристика быстродействия, определяющая, как время выполнения алгоритма $T(n)$ зависит от размера входных данных $n$.
2. Пространственная сложность — параметр, показывающий объем дополнительной памяти $S(n)$, требуемой алгоритму, помимо памяти для хранения входных данных.

Особое внимание при анализе сортировки уделяется свойству стабильности (устойчивости). Стабильность алгоритма сортировки означает, что он сохраняет относительный порядок следования элементов с одинаковыми ключами. Например, если в исходном массиве элемент $A$ стоит перед элементом $B$, и оба имеют одинаковый ключ, то в отсортированном массиве $A$ также должен стоять перед $B$. Нестабильные алгоритмы (например, QuickSort) могут нарушать этот порядок, что имеет решающее значение при работе с данными, где важен не только ключ, но и оригинальный порядок их ввода.

Математический аппарат асимптотического анализа

Для оценки эффективности алгоритмов используется аппарат асимптотических нотаций. Эти обозначения позволяют абстрагироваться от машинных констант, особенностей компилятора и языка программирования, фокусируясь исключительно на скорости роста времени выполнения при стремлении размера данных $n$ к бесконечности.

O-нотация (O-большое): Наихудший случай

O-нотация задает асимптотическую верхнюю границу функции трудоемкости $T(n)$, описывая наихудшее время работы алгоритма (worst-case complexity). Это наиболее часто используемая метрика, так как она гарантирует, что время выполнения алгоритма никогда не превысит определенный порог.

Строгое определение: Функция $f(n)$ является $O(g(n))$, если существуют положительные константы $c$ и $n_{0}$ такие, что: $f(n) \le c \cdot g(n)$ для всех $n \ge n_{0}$.

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

Ω-нотация (Омега-большое): Наилучший случай

Ω-нотация задает асимптотическую нижнюю границу функции трудоемкости, описывая наилучшее время работы алгоритма (best-case complexity).

Строгое определение: Функция $f(n)$ является Ω$(g(n))$, если существуют положительные константы $c$ и $n_{0}$ такие, что: $f(n) \ge c \cdot g(n)$ для всех $n \ge n_{0}$.

Например, для большинства алгоритмов сортировки, основанных на сравнении, наилучший случай (уже отсортированный массив) имеет сложность Ω$(n)$ (так как необходимо просмотреть каждый элемент хотя бы один раз).

Θ-нотация (Тета-нотация): Средний случай

Θ-нотация задает асимптотически точную границу (верхнюю и нижнюю одновременно), описывая, что время работы алгоритма растет пропорционально $g(n)$. Это часто используется для описания среднего времени работы алгоритма (average-case complexity), когда наихудший и наилучший случаи редки.

Строгое определение: Функция $f(n)$ является Θ$(g(n))$, если существуют положительные константы $c_{1}$, $c_{2}$ и $n_{0}$ такие, что: $c_{1} \cdot g(n) \le f(n) \le c_{2} \cdot g(n)$ для всех $n \ge n_{0}$.

Если алгоритм имеет Θ$(n \log n)$, это означает, что его время выполнения гарантированно растет с такой скоростью и не может быть существенно быстрее или медленнее (в асимптотическом смысле).

Глава 2. Детальный анализ классических алгоритмов сортировки и поиска

Быстрая сортировка (QuickSort): Механика и анализ сложности

QuickSort, изобретенный Чарльзом Хоаром, является одним из наиболее часто используемых алгоритмов сортировки благодаря своему исключительному среднему времени выполнения. Он использует стратегию «Разделяй и властвуй».

Механика:

1. Разделение (Partitioning): Выбирается опорный элемент (pivot). Массив разбивается на две части: все элементы, которые меньше опорного, перемещаются влево от него, а все элементы, которые больше — вправо. Опорный элемент оказывается на своем финальном месте.
2. Рекурсия: Алгоритм рекурсивно вызывается для подмассива слева и подмассива справа от опорного элемента.

Анализ сложности:

Сценарий	Временная сложность	Пространственная сложность	Комментарий
Средний случай	Θ($n \log n$)	$O(\log n)$	Наиболее вероятный исход. Константа перед $n \log n$ мала, что обеспечивает высокую скорость.
Наилучший случай	Ω($n \log n$)	$O(\log n)$	Возникает, когда опорный элемент делит массив ровно пополам на каждой итерации.
Наихудший случай	$O(n^2)$	$O(n)$	Возникает при неудачном выборе опорного элемента (например, всегда выбирается крайний элемент в уже отсортированном или обратно отсортированном массиве).

Пространственная сложность $O(\log n)$ обусловлена стеком рекурсивных вызовов. В худшем случае, если массив делится крайне неравномерно (на $n-1$ и $1$ элемент), глубина рекурсии достигает $n$, что требует $O(n)$ дополнительной памяти. В современных реализациях (например, Introsort) эта проблема устраняется. QuickSort не является стабильным алгоритмом.

Сортировка Шелла (ShellSort): Оптимизация сортировки вставками

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

Механика:
ShellSort сортирует элементы, находящиеся на большом расстоянии друг от друга (на расстоянии шага $h$). Это позволяет крупным элементам быстро перемещаться к своим финальным позициям, что невозможно в классической сортировке вставками. По мере выполнения алгоритма, шаг $h$ постепенно уменьшается, пока не станет равным единице, на котором выполняется финальная сортировка вставками всего массива.

Анализ сложности:
Эффективность ShellSort критически зависит от выбора последовательности шагов $h$.

Последовательность шагов	Временная сложность (Средний случай)	Временная сложность (Худший случай)
Оригинальная (Шелла)	$O(n^2)$	$O(n^2)$
Последовательность Седжвика	$O(n^{4/3})$ или $O(n^{5/4})$	$O(n^{4/3})$
Последовательность Циуры (2001)	Приближается к $O(n \cdot (\log n)^2)$	До сих пор не доказана строгая нижняя граница, эмпирически очень эффективна.

Последовательность шагов Циуры (1, 4, 10, 23, 57, 132, 301, 701…) является одной из лучших, найденных эмпирически. Для случайных данных ShellSort с этой последовательностью демонстрирует превосходные результаты по среднему числу сравнений, часто опережая QuickSort для массивов среднего размера, благодаря низким накладным расходам и пространственной сложности $O(1)$ (сортировка «на месте»). ShellSort не является стабильным.

Эффективный поиск: От линейного к бинарному поиску

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

1. Линейный поиск (Sequential Search):
   • Сложность: $O(n)$.
   • Применимость: Любой массив, независимо от упорядоченности.
   • Механика: Последовательный просмотр всех элементов до нахождения искомого.
2. Бинарный поиск (Binary Search):
   • Сложность: $O(\log n)$.
   • Применимость: Строго упорядоченные массивы.
   • Механика: В каждой итерации область поиска сокращается вдвое, путем сравнения искомого элемента с центральным элементом текущей области.

Бинарный поиск является асимптотически гораздо более эффективным, чем линейный. Например, для массива из $10^6$ элементов линейный поиск в худшем случае требует $10^6$ сравнений, тогда как бинарный поиск требует не более $\log_{2}(10^6) \approx 20$ сравнений. Разве это не убедительное доказательство того, что предварительная сортировка массива (сложность $O(n \log n)$) многократно окупается, если за ней последует большое количество запросов поиска?

Глава 3. Современные методы оптимизации и альтернативные структуры

Классические алгоритмы имеют уязвимости: QuickSort может деградировать до $O(n^2)$, а MergeSort требует $O(n)$ дополнительной памяти. Современные промышленные реализации (стандартные библиотеки C++, Java, Python) решают эти проблемы с помощью гибридных алгоритмов и более сложных структур данных.

Гибридные сортировки: Introsort и TimSort

Introspective Sort (Introsort)

Introsort — это гибридный алгоритм, разработанный Дэвидом Массером и используемый в стандартной библиотеке C++ (std::sort). Он сочетает три метода, используя преимущества каждого:

1. QuickSort: Основной алгоритм для больших массивов, обеспечивающий высокую скорость $O(n \log n)$ в среднем.
2. HeapSort (Пирамидальная сортировка): Используется для предотвращения деградации до $O(n^2)$.
3. Insertion Sort (Сортировка вставками): Используется для небольших подмассивов.

Механизм гарантированной сложности $O(n \log n)$:
Introsort начинает как QuickSort. При каждом рекурсивном вызове он отслеживает глубину рекурсии. Если глубина рекурсии превышает $\lfloor 2 \cdot \log_{2}(N) \rfloor$, где $N$ — общий размер исходного массива, алгоритм переключается на HeapSort. Это критически важно, так как HeapSort гарантированно имеет сложность $O(n \log n)$ даже в худшем случае, тем самым «спасая» QuickSort от квадратичной деградации.

TimSort

TimSort — адаптивный, стабильный, гибридный алгоритм, разработанный Тимом Питерсом, который используется в Python и Java (Arrays.sort() для объектов). Он сочетает Merge Sort и Insertion Sort.

Ключевые механизмы TimSort:

1. Поиск «Прогонов» (Runs): TimSort ищет в данных уже существующие отсортированные последовательности (runs). Это делает его адаптивным; если данные частично отсортированы, он работает быстрее.
2. Insertion Sort для MinRun: Если найденный «прогон» меньше минимального размера (MinRun, обычно от 32 до 64 элементов), он расширяется до MinRun и сортируется с помощью Insertion Sort. Это позволяет быстро упорядочить маленькие, локализованные фрагменты данных, используя преимущества сортировки вставками для малых $N$.
3. Слияние (Merge Sort): Отсортированные «прогоны» объединяются с использованием алгоритма слияния, который контролирует баланс стека для минимизации операций копирования.
4. Галопирующий режим (Galloping Mode): При слиянии двух «прогонов», если элементы одного «прогона» последовательно оказываются меньше элементов другого, TimSort переходит в «галопирующий режим». Вместо последовательного сравнения, он ищет место в другом «прогоне» с помощью бинарного поиска, что ускоряет слияние сильно различающихся по значению последовательностей.

TimSort имеет временную сложность $O(n \log n)$ в худшем случае и, благодаря адаптивности, сложность $O(n)$ в лучшем случае (когда массив уже отсортирован).

Критерий перехода (Crossover Point)

Анализ асимптотической сложности $O(n \log n)$ является точным только при $n \to \infty$. Для малых объемов данных (несколько десятков элементов) алгоритмы с более высокой теоретической сложностью, такие как Insertion Sort ($O(n^2)$), могут быть эмпирически быстрее, чем QuickSort или MergeSort.

Это объясняется двумя факторами:

1. Низкий константный множитель: Формула времени выполнения $T(n) \approx c \cdot n^2$ для Insertion Sort имеет очень маленькую константу $c$ по сравнению с $T(n) \approx c’ \cdot n \log n$ для QuickSort.
2. Накладные расходы и кеш: Рекурсивные вызовы и управление стеком QuickSort, а также выделение дополнительной памяти в MergeSort, создают значительные накладные расходы. Insertion Sort работает «на месте» и демонстрирует высокую локальность данных, что очень эффективно использует кеш процессора.

Пороговое значение (Crossover Point), при котором происходит переход от QuickSort/MergeSort к Insertion Sort, обычно устанавливается экспериментально и составляет от 7 до 50 элементов. В современных реализациях чаще всего используются значения 10, 16 или 32.

Альтернативные структуры данных для O(1) и O(log n) поиска

Если целью является не сортировка, а именно максимально эффективный поиск, то массив перестает быть оптимальной структурой, и используются альтернативы.

Хеш-таблицы (Hash Table)

Хеш-таблицы обеспечивают наилучшее среднее время поиска.

• Механика: Элемент (ключ) преобразуется в индекс массива (хеш-код) с помощью хеш-функции, что позволяет получить доступ к элементу напрямую.
• Сложность: $O(1)$ в среднем случае.
• Худший случай: $O(n)$. Возникает, когда все ключи отображаются в один и тот же индекс (коллизия).

Для разрешения коллизий используются два основных метода:

1. Метод цепочек (Separate Chaining): В каждом слоте массива хранится указатель на связанный список или, для больших объемов данных, на сбалансированное дерево, содержащее все элементы, хешированные в этот слот.
2. Открытая адресация (Open Addressing): При коллизии ищется следующий свободный слот в самом массиве по правилам пробирования (линейное, квадратичное или двойное хеширование).

Сбалансированные Бинарные Деревья Поиска (BST)

Бинарные деревья поиска (BST) обеспечивают упорядоченное хранение данных, но их эффективность зависит от баланса. Несбалансированное дерево может деградировать до связанного списка ($O(n)$). Для гарантированной сложности $O(\log n)$ используются самобалансирующиеся структуры.

Сравнение АВЛ-деревьев и Красно-черных деревьев:

Характеристика	АВЛ-дерево (AVL Tree)	Красно-черное дерево (Red-Black Tree)
Баланс	Строгий (разница высот поддеревьев не более 1).	Ослабленный (поддерживаются правила окраски узлов).
Сложность поиска	$O(\log n)$ — самая быстрая из сбалансированных структур.	$O(\log n)$ — медленнее, чем AVL на константу.
Сложность модификации (вставка/удаление)	Требует больше операций вращения для поддержания строгого баланса.	Требует меньше операций вращения. Оптимально для частого обновления.
Применение	Применяется, когда преобладает операция поиска (read-heavy).	Используется в стандартных библиотеках (std::map, Java TreeMap), где важен баланс между чтением и записью.

Таким образом, выбор структуры данных для поиска является компромиссом между временем доступа (AVL/Хеш-таблицы) и сложностью модификации (Красно-черные деревья).

Глава 4. Методика и результаты эмпирического сравнения

Методология эксперимента

Эмпирическое тестирование позволяет проверить, насколько теоретические оценки O-нотации соответствуют реальной производительности, учитывая накладные расходы, оптимизации компилятора и особенности архитектуры (кеш).

Ключевые метрики для сравнения:

1. Общее время выполнения (Elapsed Time): Измеряется в миллисекундах. Для минимизации влияния операционной системы и фоновых процессов, каждый тест должен быть повторен многократно (например, 10-100 раз), а результат усреднен.
2. Количество операций (Сравнений и Обменов): Измеряется счетчиками, встроенными в код алгоритма. Это позволяет получить «чистую» трудоемкость, независимую от скорости процессора.

Диапазон размерности данных:
Тестирование должно охватывать широкий диапазон $N$, от малого до большого, чтобы проследить динамику роста сложности: от $N=500$ (где могут доминировать простые алгоритмы) до $N=60000$ (где должна доминировать асимптотика $n \log n$).

Подготовка наборов входных данных

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

№	Тип входных данных	Назначение	Ожидаемый результат
1	Случайный набор	Оценка среднего времени (Average-case).	QuickSort, Introsort, TimSort покажут $O(n \log n)$.
2	Прямо отсортированный	Оценка наилучшего случая (Best-case).	TimSort (адаптивный) покажет $O(n)$. QuickSort (без оптимизации) может показать $O(n^2)$.
3	Обратно отсортированный	Оценка наихудшего случая (Worst-case).	QuickSort (без оптимизации) покажет $O(n^2)$. Introsort гарантирует $O(n \log n)$.
4	Частично отсортированный	Оценка адаптивности. Создание набора с большим количеством «прогонов» (runs).	TimSort покажет производительность, близкую к $O(n)$, используя механизм слияния существующих «прогонов».

Тестирование на частично отсортированных данных (пункт 4) является критически важным для оценки современных адаптивных алгоритмов. Если TimSort или Insertion Sort используются для массива, который уже на 80% отсортирован, их производительность должна резко возрасти, подтверждая эффективность их механизма.

Сравнительный анализ: Теория vs. Практика

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

Пример (гипотетический, основанный на анализе):

Алгоритм	N=500 (мс)	N=60000 (мс)	Теоретическая сложность	Обсуждение расхождений
Insertion Sort	0.05	4500.0	$O(n^2)$	Очень быстро для N=500, но взрывной рост для N=60000 (подтверждение квадратичной зависимости).
QuickSort (базовый)	0.15	18.0	$O(n \log n)$	Быстро, но нестабильно. Если тест на обратно отсортированном N=60000 показал 4000 мс, это подтвердило бы деградацию до $O(n^2)$.
Introsort	0.18	15.0	Θ($n \log n$)	Самый стабильный результат, подтверждающий гарантию $O(n \log n)$ даже в худшем случае.
TimSort	0.20	20.0	$O(n \log n)$	Чуть медленнее Introsort на случайных данных, но на частично отсортированных (тип 4) должен показать результат, близкий к $O(n)$.
ShellSort	0.10	35.0	$O(n^{4/3})$	Высокая производительность для N=500 (низкий константный множитель $O(1)$ памяти). Рост медленнее $O(n^2)$, но быстрее $O(n \log n)$.

Выводы из практического анализа:

1. Доминирование асимптотики: При больших $N$ (от 10000 и выше) алгоритмы $O(n \log n)$ всегда превосходят $O(n^2)$ и $O(n^{4/3})$, подтверждая важность асимптотического анализа.
2. Эффект Crossover Point: На малых $N$ (до 50-100) Insertion Sort или ShellSort могут быть быстрее из-за низких накладных расходов. Это полностью оправдывает использование гибридных алгоритмов.
3. Адаптивность: TimSort демонстрирует лучший результат на частично отсортированных данных, что является ключевым фактором его выбора в высокоуровневых языках.

Заключение

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

В рамках теоретической части были даны строгие математические определения асимптотическим нотациям $O$, $\Omega$ и $\Theta$, что является фундаментальной базой для оценки алгоритмической сложности. Анализ QuickSort показал его высокую эффективность в среднем случае ($O(n \log n)$) и необходимость применения защитных механизмов (как в Introsort) для исключения деградации до $O(n^2)$. ShellSort, несмотря на более слабую теоретическую границу ($O(n^{4/3})$), доказал свою практическую ценность для средних массивов за счет низких накладных расходов ($O(1)$ памяти).

Анализ современных методов оптимизации подтвердил, что будущее эффективной алгоритмизации лежит в области гибридных подходов. Introsort и TimSort являются эталонными решениями, сочетающими скорость QuickSort/MergeSort, гарантию HeapSort и эффективность Insertion Sort на малых подмассивах. В частности, механизм Introsort, переключающийся на HeapSort при превышении глубины рекурсии $\lfloor 2 \cdot \log_{2}(N) \rfloor$, демонстрирует инженерное решение проблемы худшего случая.

В части поиска было показано, что для достижения асимптотической сложности $O(1)$ или гарантированного $O(\log n)$ необходимо переходить от простого массива к специализированным структурам. Хеш-таблицы ($O(1)$ в среднем) и сбалансированные деревья (красно-черные для баланса «чтение/запись» и АВЛ для доминирования «чтения») являются ключевыми инструментами повышения производительности.

Рекомендации по выбору оптимального алгоритма:

1. Для больших объемов данных, когда стабильность не требуется: Использовать Introsort (или его аналоги), поскольку он обеспечивает гарантированную временную сложность $O(n \log n)$.
2. Для сортировки объектов или когда требуется стабильность: Использовать TimSort, который является адаптивным и демонстрирует высокую скорость на частично отсортированных данных.
3. Для малых подмассивов ($N<50$): Использовать Insertion Sort из-за его низких константных множителей и высокой локальности данных.
4. Для операций поиска с частым обновлением данных: Использовать Красно-черные деревья или Хеш-таблицы с эффективным разрешением коллизий.

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

Список использованной литературы

1. Давыдов, В. Г. Программирование и основы алгоритмизации : учеб. пособие. Москва : Высш. Шк., 2003. 447 с.
2. Клиффорд, Ш. Алгоритмы: построение и анализ. 2-е изд. Москва : Вильямс, 2005. 1296 с.
3. Кнут, Д. Искусство программирования. Т. 3: Сортировка и поиск. Москва : Вильямс, 2007. 824 с.
4. Красиков, И. В. Алгоритмы. Просто как дважды два. Москва : Эксмо, 2007. 256 с.
5. Культин, Н. Б. Самоучитель C++ Builder. Санкт-Петербург : БХВ-Петербург, 2003. 320 с.
6. Шамис, В. А. C++Builder 6. Для профессионалов. Санкт-Петербург : Питер, 2003. 797 с.
7. Алгоритмы сортировки: их сложность и выбор подходящего // Foxminded. URL: https://foxminded.ua/ (дата обращения: 24.10.2025).
8. Сортировки // Викиконспекты. Университет ИТМО. URL: https://ifmo.ru/ (дата обращения: 24.10.2025).
9. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных. URL: https://studfile.net/ (дата обращения: 24.10.2025).
10. Сравнение 6 алгоритмов сортировки: пузырьком, выбором, кучей, вставками, слиянием и быстрая // Proglib. URL: https://proglib.io/ (дата обращения: 24.10.2025).
11. Какие существуют альтернативные методы сортировки для оптимизации времени выполнения? // Вопросы к Поиску с Алисой. Яндекс. URL: https://ya.ru/ (дата обращения: 24.10.2025).
12. O-нотация — Оценка сложности алгоритмов // ulearn.me. URL: https://ulearn.me/ (дата обращения: 24.10.2025).
13. Асимптотический анализ: нотации Big-O, Omega и Theta // Ravesli. URL: https://ravesli.com/ (дата обращения: 24.10.2025).
14. Asymptotic Notation // Learn X in Y Minutes. URL: https://learnxinyminutes.com/ (дата обращения: 24.10.2025).
15. Сложность алгоритмов. Разбор Big O // Хабр. URL: https://habr.com/ (дата обращения: 24.10.2025).
16. Сложность алгоритмов: О, о, Ω, Θ. 2021 // ВКонтакте. URL: https://vk.com/ (дата обращения: 24.10.2025).
17. Быстрая сортировка (Quick sort) // IT Wiki. URL: https://it-wiki.com.ru/ (дата обращения: 24.10.2025).
18. Оценка алгоритмов сортировки // Studfile. URL: https://studfile.net/ (дата обращения: 24.10.2025).
19. Гибридная сортировка, Естественная сортировка — Сортировка Джона фон Неймана // Studbooks. URL: https://studbooks.net/ (дата обращения: 24.10.2025).
20. Описание алгоритмов сортировки и сравнение их производительности // Хабр. URL: https://habr.com/ (дата обращения: 24.10.2025).
21. Гибридные сортировки // Хабр. URL: https://habr.com/ (дата обращения: 24.10.2025).
22. Алгоритмическая сложность // Основы алгоритмов и структур данных. Hexlet. URL: https://hexlet.io/ (дата обращения: 24.10.2025).
23. ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ // Studfile. URL: https://studfile.net/ (дата обращения: 24.10.2025).
24. Теория алгоритмов // СарФТИ НИЯУ МИФИ. URL: https://sarfti.ru/ (дата обращения: 24.10.2025).
25. Анализ эффективности алгоритмов сортировки и встроенных реализаций на примере языка программирования Java // Молодой ученый. URL: https://moluch.ru/ (дата обращения: 24.10.2025).
26. Data structures Flashcards by Anna Coração // Brainscape. URL: https://brainscape.com/ (дата обращения: 24.10.2025).
27. 6. Алгоритмы и структуры данных. Деревья // Технострим. YouTube. URL: https://youtube.com/ (дата обращения: 24.10.2025).
28. Hash Table — The Most Popular Data Structure // YouTube. URL: https://youtube.com/ (дата обращения: 24.10.2025).
29. Искусство программирования. Т. 1: Основные алгоритмы // Williams Publishing. URL: https://williamspublishing.com/ (дата обращения: 24.10.2025).