Лабораторная работа 1. Поразрядная сортировка дат

Условие задачи

Требуется разработать программу, осуществляющую ввод пар «ключ-значение», их упорядочивание по возрастанию ключа указанным алгоритмом сортировки за линейное время и вывод отсортированной последовательности.

Вариант задания

Параметр	Значение
Алгоритм сортировки	Поразрядная сортировка (Radix Sort)
Тип ключа	Дата в формате DD.MM.YYYY
Тип значения	Строка фиксированной длины 64 символа

Тип ключа — дата

Дата задаётся в формате DD.MM.YYYY, где компоненты могут быть записаны без ведущих нулей. Допустимые примеры:

1.1.1
1.9.2009
01.09.2009
31.12.2009

Сортировка дат выполняется по возрастанию: сначала по году, затем по месяцу, затем по дню.

Тип значения — строка фиксированной длины

Значение представляет собой строку фиксированной длины 64 символа. Если во входных данных строка содержит меньше 64 символов, она дополняется нулевыми символами (\0) до 64 символов. Нулевые символы на экран не выводятся.

Формат входных данных

На каждой непустой строке входного файла располагается пара «ключ-значение». Ключ и значение разделены символом табуляции (\t). Пустые строки игнорируются.

<дата>\t<строка-значение>

Формат выходных данных

Выходные данные состоят из тех же строк, что и входные, за исключением пустых и порядка следования. Строки выводятся отсортированными по возрастанию даты. Относительный порядок строк с одинаковой датой сохраняется (устойчивая сортировка).

Пример

Ввод:

1.1.1	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naatt
01.02.2008	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naat
1.1.1	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naa
01.02.2008	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3na

Вывод:

1.1.1	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naatt
1.1.1	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naa
01.02.2008	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3naat
01.02.2008	n399tann9nnt3ttnaaan9nann93na9t3a3t9999na3aan9antt3tn93aat3na

Пояснение: даты 1.1.1 (1 января 1 года) предшествуют дате 01.02.2008 (1 февраля 2008 года), поэтому все записи с первой датой идут раньше. Внутри одинаковых дат порядок строк сохраняется исходным.

Алгоритм решения

Поразрядная сортировка (Radix Sort)

Поразрядная сортировка позволяет сортировать составные ключи за линейное время O(n). Идея состоит в том, чтобы последовательно сортировать элементы по каждому «разряду» ключа, начиная с наименее значимого, с помощью устойчивой сортировки.

Для даты выделяются три разряда:

Шаг	Разряд	Диапазон значений
1	День	1–31
2	Месяц	1–12
3	Год	1–max_year (максимальный год в данных)

На каждом шаге применяется сортировка подсчётом (Counting Sort) — устойчивая сортировка за O(n + k), где k — диапазон значений разряда.

Сортировка подсчётом (Counting Sort)

1. Подсчитать количество вхождений каждого значения ключа.
2. Вычислить префиксные суммы — они дают позиции элементов в выходном массиве.
3. Обойти входной массив справа налево (для сохранения устойчивости) и разместить каждый элемент на его позицию в выходном массиве.

Сложность

Характеристика	Значение
Временная	O(n) — линейная по числу записей
Пространственная	O(n + k), k — диапазон разряда

Реализация

Структуры данных

struct Date {
    int day, month, year;
};

struct Entry {
    Date date;      // разобранная дата для сортировки
    std::string line; // исходная строка для вывода
};

Парсинг даты

Дата разбирается вручную посимвольно — компоненты разделены точками. Ведущие нули не влияют на числовое значение.

Основной алгоритм

// Три прохода counting sort: день -> месяц -> год
countingSort(entries, 31,      [](const Entry& e) { return e.date.day;   });
countingSort(entries, 12,      [](const Entry& e) { return e.date.month; });
countingSort(entries, maxYear, [](const Entry& e) { return e.date.year;  });

Сборка и запуск

Требования

• Компилятор C++17 (g++ / clang++ / MSVC)

Компиляция

g++ main -o main.exe

Запуск

# Из файла
./main < input.txt

# Интерактивно (завершить ввод: Ctrl+D на Linux/Mac, Ctrl+Z на Windows)
./main

Запуск на Windows

main.exe < input.txt

Структура проекта

lab1/
├── main.cpp        # Исходный код программы
├── main.exe        # Скомпилированный исполняемый файл (Windows)
├── .gitignore      # Игнорируемые файлы Git
├── README.md       # Описание лабораторной работы
└── docs/
    ├── report.tex  # Отчёт (исходник LaTeX)
    └── rep.pdf     # Отчёт (скомпилированный PDF)