Grundy
Иконка канала Grundy

Grundy

29 подписчиков

Найти число среди 16 элементов за 4 проверки

89просмотров

Как найти число, не перебирая весь массив? Бинарный поиск каждый раз отбрасывает половину оставшегося диапазона. Находим первую шестёрку среди повторов, затем ищем отсутствующую семёрку. В каждом из этих примеров достаточно четырёх проверок среднего элемента из шестнадцати. Попробовать на своём массиве и посмотреть код: https://grundyjs.ru/algorithms/binary-search/?utm_source=rutube&utm_medium=social&utm_campaign=binary_search&utm_content=vertical Массив должен быть отсортирован заранее. Показанный вариант возвращает первое вхождение: даже после совпадения поиск продолжается слева. Время поиска — O(log n), дополнительная память самого алгоритма — O(1). Озвучка автора. Визуализация — AlgiViz, запись видео со звуком — CanvasTake. #бинарныйпоиск #алгоритмы #binarysearch
Почему сортировка выбором неустойчива? Один обмен наглядно

128просмотров

Две одинаковые двойки — фиолетовая и голубая. Один обмен с минимумом меняет их взаимный порядок. Так выглядит неустойчивость сортировки выбором. Попробуйте свой массив: https://grundyjs.ru/algorithms/selection-sort/?utm_source=rutube&utm_medium=social&utm_campaign=selection_sort&utm_content=instability_experiment_vertical Авторская озвучка. Визуализация — AlgiViz, запись — CanvasTake. #алгоритмы #сортировка #программирование
Пирамидальная сортировка: дерево внутри массива | AlgiViz #Shorts

117просмотров

Heap sort по шагам: строим максимальную кучу, извлекаем максимум и просеиваем новый корень. Интерактивный разбор и код: https://grundyjs.ru/algorithms/heap-sort/?utm_source=rutube&utm_medium=social&utm_campaign=heap_sort&utm_content=vertical Построение O(n), худшее время O(n log n). Итеративный алгоритм на месте требует O(1) дополнительной памяти, без учёта копии входа и истории визуализации. Сортировка неустойчива. Визуализация: AlgiViz. Запись MP4: CanvasTake. Без звука. #алгоритмы #сортировка #heapsort #AlgiViz
Быстрая сортировка: Трёхстороннее разбиение | AlgiViz #Shorts

142просмотра

Трёхстороннее разбиение — Quick sort по шагам. Группируем значения меньше, равные и больше опорного. После обмена справа проверяем пришедший элемент; рекурсия пропускает равную область. Интерактивный разбор и код обоих вариантов: https://grundyjs.ru/algorithms/quick-sort/?utm_source=rutube&utm_medium=social&utm_campaign=quick_sort&utm_content=three_way_vertical В среднем на случайных перестановках различных значений — Θ(n log n), в худшем случае — Θ(n²). Оба варианта нестабильны. Визуализация: AlgiViz. Запись: CanvasTake. Видео без звука. Русские субтитры доступны отдельной дорожкой на YouTube. #алгоритмы #сортировка #quicksort #AlgiViz
Быстрая сортировка: Разбиение Ломуто | AlgiViz #Shorts

5просмотров

Разбиение Ломуто — Quick sort по шагам. Берём последний элемент опорным, переносим меньшие значения влево и ставим опорный на окончательную позицию. Интерактивный разбор и код обоих вариантов: https://grundyjs.ru/algorithms/quick-sort/?utm_source=rutube&utm_medium=social&utm_campaign=quick_sort&utm_content=lomuto_vertical В среднем на случайных перестановках различных значений — Θ(n log n), в худшем случае — Θ(n²). Оба варианта нестабильны. Визуализация: AlgiViz. Запись: CanvasTake. Видео без звука. Русские субтитры доступны отдельной дорожкой на YouTube. #алгоритмы #сортировка #quicksort #AlgiViz
Сортировка слиянием за 87 секунд — вертикальная визуализация

4просмотра

Сортировка слиянием на примере 10 элементов: деление массива, слияние через буфер и сохранение порядка равных значений. Интерактивные алгоритмы: https://grundyjs.ru/algorithms/merge-sort/?utm_source=rutube&utm_medium=social&utm_campaign=merge_sort&utm_content=vertical 0:00 Идея алгоритма 0:06 Деление и слияние 1:07 Стабильность 1:13 Время и память 1:21 Попробуйте сами Время этой реализации — Θ(n log n), дополнительная память — O(n). История анимации хранится отдельно. Без звука. Визуализация — AlgiViz, запись MP4 — CanvasTake. #алгоритмы #сортировка #программирование
Сортировка выбором за 42 секунды — вертикальная визуализация

232просмотра

Ищем минимум, ставим его на место и расширяем отсортированный префикс. Сортировка выбором на примере [5, 2, 4, 2, 1]: шаги, нестабильность и сложность. При любом порядке входа — n(n − 1)/2 сравнений, время Θ(n²), до n − 1 обменов. Попробуйте свой массив: https://grundyjs.ru/algorithms/selection-sort/?utm_source=rutube&utm_medium=social&utm_campaign=selection_sort&utm_content=vertical Без звука, с пояснениями в кадре. Визуализация — AlgiViz, запись напрямую в MP4 — CanvasTake. #алгоритмы #сортировка #программирование
Пузырьковая сортировка за 41 секунду — вертикальная визуализация

7просмотров

Сравниваем соседей, меняем их местами — и самый большой элемент оказывается справа. Если за проход не было обменов, останавливаемся. Пузырьковая сортировка на примере [5, 2, 4, 2, 1]: шаги, стабильность и сложность. Попробуйте свой массив: https://grundyjs.ru/algorithms/bubble-sort/?utm_source=rutube&utm_medium=social&utm_campaign=bubble_sort&utm_content=vertical Без звука, с пояснениями в кадре. Визуализация — AlgiViz, запись — CanvasTake. #алгоритмы #сортировка #программирование
Сортировка вставками за 44 секунды — вертикальная визуализация

6просмотров

Берём следующий элемент, сдвигаем большие элементы вправо и вставляем ключ на его место. Так работает сортировка вставками. В ролике: шаги на примере [5, 2, 4, 2, 1], стабильность и сложность O(n²). Попробуйте свой массив в интерактивной визуализации: https://grundyjs.ru/algorithms/insertion-sort/?utm_source=rutube&utm_medium=social&utm_campaign=insertion_sort&utm_content=vertical Без звука, с пояснениями в кадре. Визуализация — AlgiViz, запись — CanvasTake. #алгоритмы #сортировка #программирование