Сортировка, которая выбрасывает неудобные элементы
Обычная сортировка переставляет элементы, чтобы сохранить весь набор. Здесь действует другой принцип: алгоритм читает данные слева направо и оставляет элемент, только если тот продолжает нужный порядок. Для возрастающей последовательности это значит: очередное число должно быть не меньше последнего сохранённого. Иначе его сразу удаляют.
Например, из `3, 1, 2, 4` останутся `3, 4`: после первой тройки числа 1 и 2 нарушают выбранное правило, а 4 подходит. Результат упорядочен, но значительная часть исходных данных потеряна.
Почему решение нельзя исправить позже
Ключевое ограничение — алгоритм не возвращается к удалённым элементам и не переставляет уже просмотренные. Он принимает решение по текущему состоянию: подходит ли новый элемент к тому, что удалось сохранить до него. Поэтому ранний выбор может повлиять на дальнейший результат. В примере, если бы алгоритм сохранил 1 вместо 3, можно было бы оставить и 2, и 4.
Это не способ получить наиболее длинную упорядоченную подпоследовательность — то есть максимально большой набор элементов в прежнем порядке. Для такой цели пришлось бы оценивать варианты, а не удалять неподходящее немедленно.
Когда такая цена имеет смысл
Подобный подход годится, если важнее быстро получить последовательность без нарушений, чем сохранить каждое значение: например, при предварительной очистке потока данных по простому правилу. Он может быть быстрым и не требовать хранения всего набора, но платой становится необратимая потеря информации. Поэтому слово «сортирует» здесь описывает итоговый порядок, а не привычное упорядочивание исходных элементов.
