О нас 
Array
(
    [0] => Наша методика
    [1] => /about/method/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Наша методика
Array
(
    [0] => Преимущества
    [1] => /about/advantage/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Преимущества
Array
(
    [0] => Наши преподаватели
    [1] => /about/teachers/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Наши преподаватели
Array
(
    [0] => Контакты
    [1] => /about/contacts/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Контакты
Блог
Материалы 
Array
(
    [0] => Как готовиться к ЕГЭ?
    [1] => /materials/exam-prepare/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Как готовиться к ЕГЭ?
Array
(
    [0] => Учебные материалы
    [1] => /materials/learning/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Учебные материалы
Array
(
    [0] => Образовательным организациям
    [1] => /materials/partners/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Образовательным организациям
Array
(
    [0] => Пользовательское соглашение
    [1] => /materials/agreement/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Пользовательское соглашение
Справочник 
Array
(
    [0] => Арифметика
    [1] => /arithmetic/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Арифметика
Array
(
    [0] => Алгебра
    [1] => /algebra/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Алгебра
Array
(
    [0] => Планиметрия
    [1] => /planimetry/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Планиметрия
Array
(
    [0] => Информатика
    [1] => /informatics/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Информатика
Array
(
    [0] => Русский язык
    [1] => /russian/
    [2] => Array
        (
        )

    [3] => Array
        (
            [class] => 
        )

    [4] => 
)
Русский язык
Контакты
Личный кабинет
8 800 551-50-78 (бесплатно)
БЕСПЛАТНАЯ ПОДГОТОВКА К ЕГЭ ПО ПРОФИЛЬНОЙ МАТЕМАТИКЕ
Подготовься к ЕГЭ-2026 по профильной математике самостоятельно с помощью сервиса "1С:Репетитор"!
Понятная теория и эффективные тренажеры с объяснением! Вы успеете подготовиться к экзамену! Начните занятия прямо сейчас!
design_arrow
8 800 551-50-78
Личный кабинет
1С:Репетитор – подготовка к ЕГЭ по математике
© ООО «1С-Софт» | ЧОУ ДПО «1С-ОБРАЗОВАНИЕ» | 2016–2025
8 800 551-50-78
Связаться с нами:
Мы в мессенджерах:
Мы в соцсетях:
Алгоритмы внешней сортировки

Алгоритмы внешней сортировки

Внешняя сортировка применяется, когда объём данных существенно превышает объём оперативной памяти и приходится хранить их на внешних носителях (диск, SSD, сеть). В отличие от «внутренних» алгоритмов (QuickSort, HeapSort, MergeSort в ОЗУ), здесь доминирует стоимость операций ввода-вывода (I/O): чтений и записей блоков данных.
Для подготовки к ЕГЭ тема полезна тем, что объединяет:

  • моделирование систем (память–процессор–диск);

  • асимптотический анализ с нетривиальной метрикой (число I/O, а не только сравнения);

  • проектирование алгоритмов «разделяй и властвуй» и строгие правила работы с ресурсами.

Модель и обозначения (академический минимум)

Рассмотрим упорядочивание N записей (ключ+запись) при оперативной памяти M записей и блочном вводе-выводе размером B записей (обычно десятки/сотни КБ).

  • Одно чтение/запись обрабатывает целый блок из B записей.

  • Внутрипамятная сортировка (на куске размером ≤M) считаем «дешёвой» относительно операций I/O.

  • Общая стоимость оцениваем по числу прочитанных/записанных блоков (I/O-модель).

Инварианты внешней сортировки:

  1. Данные читаются/пишутся только блоками размера B.

  2. В любой момент в ОЗУ одновременно находится не более M записей (включая буферы).

  3. Алгоритм обязан быть устойчивым по отношению к I/O-ошибкам: если этап прерван, его можно повторить (журналирование/временные файлы).

Базовая стратегия: «серии → многочёрговое (k-путевое) слияние»

Практически все современные внешние сортировки строятся из двух фаз:

Фаза A. Генерация начальных серий (runs)

  1. Читаем последовательно порции данных, каждая порция не превышает M записей.

  2. Сортируем её в памяти любой устойчивой внутриядерной сортировкой (часто Timsort/мердж).

  3. Записываем отсортированный фрагмент на диск как начальную серию.
    Если вход «случаен», можно увеличить среднюю длину серии с помощью replacement selection (селекция с заменой): поддерживается мин-куча размером ~M; каждая пришедшая запись либо продолжает текущую серию, либо откладывается в следующую. Это даёт ожидаемую длину серии около 2M.

Правило 1 (серии): если допускается усложнение, применяйте replacement selection; иначе – простое «считать-отсортировать-выписать» блоками по M.

Фаза B. Многопутевое (k-путевое) слияние серий

Пусть образовалось r начальных серий. Выделим k входных буферов и 1 выходной буфер (итого k+1 буферный блок; плюс служебные структуры), что требует (k+1)⋅B≤M.

Алгоритм одномоментно сливает k серий в одну более длинную, проводя последовательность проходов (passes), пока не останется одна серия–итоговый отсортированный файл.

Число проходов (без фазы A):
Число проходов (без фазы A)

Варианты слияния и планирование проходов

Сбалансированное k-путевое слияние. На каждом проходе серии равномерно разбиваются на группы по k и сливаются.
Полифазное (polyphase) слияние. Серии распределяются по нескольким «лентам» (файлам) в количествах, близких к последовательности Фибоначчи, чтобы минимизировать число «пустых» серий и проходов. Актуально для минимизации I/O при ограниченных файловых дескрипторах.

Правило 3 (план): если число открытых файлов не ограничивает, используйте обычное сбалансированное k-слияние; при строгих ограничениях (исторически – «ленты») полезны полифазные схемы.

Буферизация и инженерные приёмы

  • Двойная буферизация (double buffering): пока процесс сравнивает элементы в первом наборе буферов, второй набор асинхронно подкачивается/сбрасывается – сокращаем простои.

  • Размер блока B: должен быть кратен размеру страницы и оптимален для устройства (обычно 128–1024 КБ для HDD; для SSD чуть меньше чувствительно, но крупные блоки всё равно выгодны).

  • Структура выбора минимума: турнирное дерево (winner tree) даёт O (log k) на выбор следующего минимального ключа; для малых k достаточно двоичной кучи.

  • Стабильность: внешняя сортировка на основе слияния по определению стабильна, что важно при сортировке по составным ключам (вторичный ключ сохраняет порядок).

Правило 4 (устойчивость): если требуется стабильность, используйте k-путевое слияние; избегайте внешнего «пирамидального» подхода, нарушающего порядок равных ключей.

Оценка сложности в I/O-модели
Оценка сложности в I/O-модели
Информатика–схема классификации методы внешней сортировки

Практические «правила чистой реализации»

  1. Разделяйте код на этапы: генерация серий ↔ слияние; логируйте прогресс (r, k, pass).

  2. Проверяйте инварианты: (k+1)B ≤ M; буферы не пересекаются; стабильность сохранена.

  3. Не держите лишнее в памяти: только буферы и структура выбора минимума.

  4. Обрабатывайте хвосты: последняя группа может содержать <k серий – алгоритм должен корректно их сливать.

  5. Тестируйте на крайних случаях: все ключи равны; уже отсортировано; обратный порядок; огромные записи; отсутствие места на диске.

  6. Безопасность данных: пишите в новый файл; после успешного прохода – атомарная переименовка (fail-safe).

Иллюстративный пример (k-слияние)
Иллюстративный пример (k-слияние)

Связь с подготовкой к ЕГЭ

  • Алгоритмизация: декомпозиция задачи (серии → слияние) и инварианты корректности.

  • Оценки сложности: работа с логарифмами и потолками/полами при подсчёте проходов.

  • Модели вычислений: понимание, что метрика «время» ≠ «количество сравнений», а определяется узким местом (I/O).

  • Строки/записи: устойчивое слияние критично для составных ключей – типичный формат задач.
    Даже если в ЕГЭ нет прямой реализации внешней сортировки, эти рассуждения усиливают способность анализировать алгоритмы и ресурсы.

Пять упражнений (академический формат)

Упражнение 1. Подсчёт проходов.

Упражнение 2. Влияние replacement selection.
В условиях упражнения 1 предположите L≈2M. Пересчитайте r, P, общее I/O. Сформулируйте вывод о целесообразности применения селекции с заменой при случайном входе.

Упражнение 3. Буферизация и выбор структуры.
Пусть k=64. Сравните два варианта выбора минимума: двоичная куча и турнирное дерево.

а) Оцените асимптотику на выбор следующего элемента. б) Объясните, почему даже одинаковая асимптотика может давать разные константы времени. в) Приведите аргументы в пользу double buffering.

Упражнение 4. Стабильность и вторичные ключи.
Нужно отсортировать по ключу «Дата» и при равенстве дат сохранить исходный порядок «ID».

а) Объясните, почему k-путевое слияние стабильно. б) Предложите тест, доказывающий сохранение стабильности на внешних данных (описать вход/ожидаемый выход). в) Укажите типичный дефект реализации, разрушающий стабильность.

Упражнение 5. Планирование при ограничении открытых файлов.
ОС позволяет держать открытыми не более 16 файлов. Предложите план полифазного слияния для r = 100 серий: а) схема распределения по «лентам» (файлам), б) порядок проходов, в) как избежать «фиктивных» серий или минимизировать их число. Дайте качественную оценку выигрыша относительно наивного «слияния по 15».

Заключение

Внешняя сортировка – это строгое применение принципа «разделяй и властвуй», оптимизированное под I/O-реальность: длинные начальные серии и широкое k-слияние минимизируют число проходов, а грамотная буферизация и стабильные процедуры слияния обеспечивают предсказуемость и корректность. Разобрав модель, инварианты и правила планирования, учащийся получает не только алгоритмическое мастерство, но и системное мышление, критичное для успешного выполнения заданий ЕГЭ и для дальнейшей инженерной практики.


< Назад к списку