
                            class Algorithms {
                            public:
                                Algorithms lecture {
                                    .author = "Р.А. Нестеров"
                                    .year = "2026/27"
                                    .course = "НИУ ВШЭ ПИ, 2 курс"
                                };

алгоритмы
и структуры данных


                                // 01. Сортировка подсчетом
                                void bucket_sort(std::vector<int>& vec);
                                void counting_sort(std::vector<int>& vec);


                                // 02. LSB-поразрядная сортировка и варианты ее реализации
                                void radix_sort(std::vector<int>& vec);


                                // 03. Домашняя работа set_3: применение библиотеки Google Benchmark
                                // для многостороннего бенчмаркинга алгоритмов
                                void fetch_new_tasks();

->07

07.00

краткая ретроспектива и повторение

алгоритмы сортировки на основе сравнений
[cb-сортировки]

классификация алгоритмов сортировки


                       void comparisons_lower_bound();

дерево решений для сортировки

явная оценка высоты дерева решений cb-сортировки

утверждение 06.03

асимптотическая нижняя граница высоты $h$ дерева решений для cb-сортировки составляет $\Omega(n \log n)$

ключевое следствие

алгоритм сортировки merge_sort является оптимальным
алгоритм сортировки heap_sort является оптимальным


                       void classify_sorting_algorithms();

классификация сортировок

ключевые параметры сравнения алгоритмов

внутренняя

алгоритм и входные данные полностью помещаются в оперативную память [RAM]
число I/O-операций с диском не зависит от размера входных данных [загрузить и выгрузить]

внешняя

блоки входных данных поочередно выгружаются в оперативную память для сортировки
алгоритм нацелен на минимизацию числа I/O-операций с диском при разбиении данных на блоки и их слиянии


                       void classify_sorting_algorithms();

классификация сортировок

ключевые параметры сравнения алгоритмов

по месту, in-place

объем дополнительной памяти, необходимой алгоритму,
не зависит от размера входных данных
пространственная сложность
$\mathrm{O}(1)$, $\mathrm{O}(\log n)$, ...

с дополнительной памятью

объем дополнительной памяти, необходимой алгоритму,
определяется размером входных данных
пространственная сложность
$\mathrm{O}(n)$, $\mathrm{O}(n \log n)$, ...


                       void classify_sorting_algorithms();

классификация сортировок

ключевые параметры сравнения алгоритмов

устойчивая, stable

алгоритм сохраняет исходный порядок следования эквивалентных объектов

[(8, fox), (9, dog), (4, wolf), (8, cow)] [(4, wolf), (8, fox), (8, cow), (9, dog)]

неустойчивая, unstable

алгоритм может нарушить исходный порядок
следования эквивалентных объектов

[(8, fox), (9, dog), (4, wolf), (8, cow)] [(4, wolf), (8, cow), (8, fox), (9, dog)]

insertion_sort.cpp

                                    
                                        #include <vector>
                                        void insertion_sort(std::vector<int>& arr) { 
                                            int n = arr.size();
                                            for (int i = 1; i < n; ++i) {  
                                                int key = arr[i];
                                                int j = i - 1;  
                                                while (j >= 0 && arr[j] > key) {
                                                    arr[j + 1] = arr[j];
                                                    j = j - 1; 
                                                }
                                                arr[j + 1] = key;
                                            }
                                        }

утверждение 08.01

алгоритм insertion_sort является устойчивым

quick_sort.cpp

                                    
                                        #include <vector>
                                        #include <algorithm>
                                        #include <iterator>

                                        template<typename Iter>
                                        void quick_sort(Iter first, Iter last) {
                                            if (std::distance(first, last) <= 1) return;
                                            
                                            auto pivot_pos = partition(first, last);
                                            
                                            quick_sort(first, pivot_pos);
                                            quick_sort(std::next(pivot_pos), last);
                                        }

утверждение 08.01

алгоритм quick_sort не является устойчивым

Алгоритм	Аналог в STL	IN-PLACE?	stable?	Худший случай	Примечание
selection_sort	—	✅	❌	$\mathrm{O}(n^2)$	—
insertion_sort	—	✅	✅	$\mathrm{O}(n^2)$	полезно для небольших массивов и тех, что уже упорядочены
shell_sort	—	✅	❌	$\mathrm{O}(n^{1.5})$	—
merge_sort	std::stable_sort	❌	✅	$\mathrm{O}(n \log n)$	устойчивый алгоритм с гарантированной сложностью
quick_sort	std::sort	✅	❌	$\mathrm{O}(n^2)$	вероятностная гарантия оптимальной сложности
heap_sort	std::make_heap std::sort_heap	✅	❌	$\mathrm{O}(n \log n)$	НЕустойчивый алгоритм с гарантированной сложностью

*std::nth_element для поиска порядковой статистики

*std::partial_sort для выборки заданного числа наименьших элементов массива [in-place]

неделя №9
--> квиз Л6


                       void classify_sorting_algorithms();

классификация сортировок

ключевые параметры сравнения алгоритмов

на сравнениях

требуется определение полного порядка на множестве упорядочиваемых объектов
известная нижняя граница сложности — $\Omega(n \log n)$

нишевые, линейные

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

07.01

сортировка подсчетом

базовая схема алгоритма bucket_sort
для сортировки массива уникальных объектов

алгоритм counting_sort для сортировки
массива объектов с повторениями


                       void bucket_sort(std::vector<int>& arr);

сортировка номеров телефонов

массив уникальных чисел в известном диапазоне

задача 08.01

требуется отсортировать большое количество телефонных номеров — около 10 миллионов записей
телефонные номера являются уникальными
и состоят из семи цифр

проблемы quick_sort

весь массив необходимо выгружать в оперативную память [потенциальные трудности масштабирования]
для 10 миллионов семизначных чисел потребуется
$10^7 \cdot 32$ бита $\approx 38.1$ мегабайт


                       void bucket_sort(std::vector<int>& arr);

сортировка номеров телефонов

массив уникальных чисел в известном диапазоне

задача 08.01

требуется отсортировать большое количество телефонных номеров — около 10 миллионов записей
телефонные номера являются уникальными
и состоят из семи цифр

схема алгоритма bucket_sort

создаем битовый вектор A размера $10^7$, что потребует
$10^7 \colon 2^3 \colon 2^{10} \colon 2^{10} = 1.2$ мегабайт [выигрыш более 30 раз]
для каждого номера phone устанавливаем A[phone] = 1
выводим индексы A, для которых A[phone] == 1

сложность $\Theta(n+m)$ — псевдолинейная


                       void bucket_sort(std::vector<int>& arr);

сортировка номеров телефонов

массив уникальных чисел в известном диапазоне

схема алгоритма bucket_sort

создаем битовый вектор A размера $10^7$, что потребует
$10^7 \colon 2^3 \colon 2^{10} \colon 2^{10} = 1.2$ мегабайт [выигрыш более 30 раз]
для каждого номера phone устанавливаем A[phone] = 1
выводим индексы A, для которых A[phone] == 1

сложность $\Theta(n+m)$ — псевдолинейная

ограничения bucket_sort

алгоритм не применяется для произвольных данных: нам известен диапазон $[\min, \max]$, в который они попадают
если во входных данных есть повторения, то простого битового вектора становится недостаточно

обладает ли counting_sort
этими свойствами

* клик по ответу покажет, верный ли он

обеспечивает устойчивость по умолчанию
позволяет сортировать отрицательные числа
позволяет сортировать вещественные числа

07.02

LSB-поразрядная сортировка

поразрядная сортировка на основе массива очередей

экономичная [по памяти] поразрядная сортировка двоичных чисел: «двусторонний» массив


                       void radix_sort(std::vector<int>& arr);

сортировка десятизначных чисел

массив чисел / строк в известном алфавите

задача 08.02

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

проблемы counting_sort

весь массив счетчиков необходимо выгружать в оперативную память [потенциальное исчерпание ее емкости]
хранение $10^{10}$ однобайтовых счетчиков потребует
$10^{10} \colon 2^{10} \colon 2^{10} \colon 2^{10} \approx 9.3$ гигабайта


                       void radix_sort(std::vector<int>& arr);

сортировка десятизначных чисел

массив чисел / строк в известном алфавите

задача 08.02

требуется отсортировать массив, содержащий больше количество целых чисел [основание системы счисления $B$]
числа содержат повторения и состоят из десяти цифр [можно дополнить ведущими нулями]

схема алгоритма radix_sort

выбираем устойчивый линейный алгоритм
[cb-сортировки — другой класс сложности]
пошагово упорядочиваем разряды в порядке от младшего разряда к старшему [LSB — least significant byte]

сложность $\mathrm{O}(\ell \cdot (n + B))$ — псевдолинейная