Информатика · учебный маршрут

Сортировки и сравнение строк

Проследите перестановки элементов и состояние алгоритма. Сравните способы работы с порядком и с общими фрагментами строк.

Синие фигурные скобки держат между собой оранжевый квадрат.

Чему научитесь

Различать шаг алгоритма, его инвариант и итог; проверять стоимость исправления строки.

Что пригодится

  • Индексы массива
  • Цикл и сравнение значений

10 тем по порядку

Читайте объяснение или сразу переходите к заданию

  1. Сортировка вставками: как элемент находит место в готовом префиксе

    Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.

    Практика
  2. Слияние отсортированных частей: два указателя и стабильность

    Слияние двух готовых массивов: сравнение первых оставшихся элементов, обработка хвоста и правило стабильности при равенстве.

    Практика
  3. Разбиение около опорного: что гарантирует один шаг быстрой сортировки

    Что делает разбиение около опорного элемента: области меньше, равно и больше, их инварианты и границы обещания одного шага.

    Практика
  4. Сортировка подсчётом: диапазон значений важнее числа разрядов

    Сортировка подсчётом: частоты целых ключей, сдвиг отрицательного диапазона и отличие числа значений от ширины диапазона.

    Практика
  5. Поразрядная сортировка: зачем каждому проходу стабильность

    LSD-сортировка по разрядам: проход от единиц к старшим цифрам, сохранение прежнего порядка и границы числовой модели.

    Практика
  6. Порядковая статистика: найти k-й элемент без полной сортировки

    Поиск k-го наименьшего элемента: локальный ранг после разбиения, повторяющиеся значения и выбор только нужной области.

    Практика
  7. Префикс-функция: как искать границу совпавшего фрагмента

    Префикс-функция строки: собственная граница, суффикс обработанного префикса и переход к более короткому совпадению.

    Практика
  8. Z-функция строки: длины совпадения с её началом

    Z-функция без путаницы с префикс-функцией: совпадение от текущей позиции, правая граница известного блока и длина результата.

    Практика
  9. Скользящий хеш: быстро сравнить кандидатов и проверить совпадение

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

    Практика
  10. Расстояние редактирования: вставить, удалить или заменить символ

    Как получается расстояние Левенштейна: префиксы строк, вставка, удаление, замена и проверка минимального пути.

    Практика

Как заниматься

Нужно проходить все темы подряд?

Последовательность помогает связать понятия, но можно открыть любую тему. Если задача уже знакома, начните с практики: ответ сопровождается объяснением.

Что делать, если ответ оказался неверным?

Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.

Все темы: Информатика