Please enable JavaScript.

Coggle requires JavaScript to display documents.

Алгоритмы - Coggle Diagram

- - - - Извлечь 2 первых
      - Соединить пустым родителем
      - Вернуть в очередь с суммарным приоритетом
- - - - Основана на функции Partition, группирующей элементы на меньшие и большие, чем pivot
      - pivot
        
        Популярна медиана из трех элементов: крайних и центрального
        
        Задается эвристически
        
        Опорное значение
      - Рекурсивный вызов на группах, разделенных pivot
    - - Две отсортированные группы сливаются в одну копированием в буфер наименьшего из двух очередных
      - Дополнительная память для буфера равна размеру исходного массива
      - Работает рекурсивно путем деления групп пополам
      - Мало сравнений взаимоудаленных элементов (эффективно при использовании блоков HDD)
    - - Обобщение метода вставки
        
        Если k = 1, это обычный метод вставки
        
        Метод вставки для каждого k-го
        
        k-сортировка для всех k смещений
      - Предварительные сортировки
        
        Ускоряют завершающую
        
        Приближают элементы к их конечным позициям
      - Последовательность k
        (шагов сортировки)
        
        Задается эвристически (н-р, последовательность Кнута)
        
        Должна завершаться числом 1
    - - Концептуально, вставка всех в пирамиду и последовательное извлечение
      - Пирамида
        
        Жестко сбалансированное бинарное дерево
        
        Может быть представлена массивом для сортировки "на месте"
        
        Дочерние узлы всегда меньше родительского
      - Балансировка
        
        При вставке элемент размещается в конец и "поднимается"
        
        "Подъем" и "спуск" схожи с сортировкой вставками
        
        При извлечении вершины, последний элемент встает на ее место и "спускается" по наименьшему
    - - Группировка по разряду (в связные списки) с возвратом в массив
      - Не требует сравнений
      - Асимптотика пропорциональна числу разрядов
    - - Битонная последовательность - отсортированная горка (в алгоритме вершина всегда в центре)
      - Шаг рекурсии
        
        ASC cортировка левой половины
        
        DESC cортировка правой половины
        
        Слияние половин
        
        Шаг сортировки Шелла при k = N / 2 (перемещает элементы в их конечные половины)
        
        Рекурсия слияния на левой и правой половинах
      - Работает только для 2^n элементов
  - - - Поиск минимального из оставшихся
      - swap минимального и занимающего его место
      - Левые конечно отсортированы
    - - Самый эффективный из тривиальных
        
        Преимущество при частичной отсортированности
        
        Завершающий этап некоторых нетривиальных методов
      - Итерация
        
        Вставка очередного в отсортированную группу
        
        Сдвиг элементов справа до образовавшейся дырки
    - - "Всплытие" наибольшего из оставшихся
      - swap на каждом смещении
      - Правые конечно отсортированы
- - - - In-order
        
        Ветка - Узел - Ветка
        
        Порядок обхода дерева поиска
      - Post-order
        
        Ветки - Узел
        
        Если узлу нужно что-то узнать о ветках
      - Pre-order
        
        Узел - Ветки
    - - Требует явное использование стека
      - Можно обойтись без стека, используя parent ссылки