Сортировки
Bubble Sort
Сортировка пузырьком
Классика жанра: соседние элементы сравниваются и меняются местами,
а наибольшие "всплывают" в конец массива.
Selection Sort
Сортировка выбором
Находим самый маленький элемент в неотсортированной части и ставим его на правильное место. Минимум обменов.
Insertion Sort
Сортировка вставками
Берем элементы по одному и вставляем их в правильное место отсортированной части массива. Отлично работает на почти отсортированных данных.
Shell Sort
Сортировка Шелла
Улучшенная сортировка вставками: элементы сравниваются и обмениваются на больших расстояниях, которые постепенно уменьшаются до единицы.
Merge Sort
Сортировка слиянием
Разделяй и властвуй: массив рекурсивно делится пополам,
а затем отсортированные половины сливаются обратно.
Quick Sort
Быстрая сортировка
Разделяй и властвуй: опорный элемент делит массив на меньшие
и большие. Две схемы разбиения - Хоара и Ломуто.
Counting Sort
Сортировка подсчетом
Сортировка без единого сравнения: считаем, сколько раз встречается
каждое значение, и собираем результат.
Heap Sort
Пирамидальная сортировка
Массив как двоичное дерево: строим кучу, забираем максимум
из корня и просеиваем новый. O(n log n) на любых данных.
Cycle Sort
Сортировка циклами
Минимум записей в массив: каждый элемент записывается ровно один раз на свое финальное место через циклы перестановок.
Radix Sort
Поразрядная сортировка
Сортировка по разрядам: числа распределяются по корзинам 0..9 последовательно от младшего разряда к старшему.
Bucket Sort
Блочная сортировка
Распределение элементов по корзинам-диапазонам с последующей сортировкой внутри корзин и сборкой в единый результат.
Tournament Sort
Турнирная сортировка
Построение турнирной сетки на выбывание: элементы играют матчи, чемпион забирается в корень, а матчи переигрываются за O(log n).
External Merge Sort
Внешняя сортировка
Для данных, не влезающих в оперативную память: нарезаем файл на отсортированные прогоны, затем сливаем их через буфер.
Timsort
Сортировка Timsort
Адаптивный гибрид вставок и слияния: находит естественные прогоны, добирает их вставками и эффективно сливает.
Поиск
Linear Search
Линейный поиск
Простой перебор: идем по массиву слева направо, пока не встретим
искомое. Данные могут быть любыми, но цена - O(n).
Binary Search
Двоичный поиск
Отсортированный массив делится пополам на каждом шаге: элемент
среди миллиона находится за 20 сравнений. O(log n).
Основы алгоритмов
Каждая анимация написана нами с нуля: никаких тяжелых библиотек, только чистый JavaScript. Можно менять набор данных (случайный, почти отсортированный, обратный и другие), регулировать скорость и ходить по шагам вперед и назад. Раздел постоянно растет: впереди наглядные структуры данных, деревья и алгоритмы на графах, а со временем - и самые неожиданные уголки информатики.