Дискретный анализ ← ЛабораторныеЛабораторная работа №1

Сортировка за линейное время

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

Вариант задания определяется типом ключа (и соответствующим ему методом сортировки) и типом значения.

Упрощенный вариант

Ключи: числа от 0 до 105, значения: буквы латинского алфавита, алгоритм: сортировка подсчетом.

Формат входных и выходных данных такой же, как в обычных вариантах.

Решение отправляется в письме с темой da:10

Типы ключей

Сотрировка подсчетом

  1. Числа от 0 до 65535.
  2. Почтовые индексы.

Поразрядная сортировка

  1. Числа от 0 до 264 - 1.
  2. Даты в формате DD.MM.YYYY, например: 1.1.1, 1.9.2009, 01.09.2009, 31.12.2009.
  3. MD5-суммы (32-разрядные шестнадцатиричные числа).
  4. Телефонные номера, с кодами стран и городов в формате
    +<код страны>-<код города>-телефон.
  5. Автомобильные номера в формате A 999 BC (используются буквы латинского алфавита).

Карманная сортировка

  1. Числа от 0 до 264 - 1.
  2. Вещественные числа в промежутке [—100, 100].

Типы значений

  1. Строки фиксированной длины 64 символа, во входных данных могут встретиться строки меньшей длины, при этом строка дополняется до 64-х нулевыми символами, которые не выводятся на экран.
  2. Строки переменной длины (до 2048 символов).
  3. Числа от 0 до 264 - 1.

Входные данные

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

Выходные данные

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

Пример

Ниже приведён пример входных и выходных данных для сортировки телефонных номеров со строками переменной длины.
Входной файл
+7-499-1582977 Moscow Aviation Institute
+7-495-6063602 Presidential Executive Office
+7-495-2242222 Federal Security Service
+375-225-449732 Babruisk hot line
+7-495-9631102 P. B. Gannushkin Moscow City Clinical Psychiatric Hospital
+7-903-5388412 "Pray to God" service
Выходной файл
+7-495-2242222 Federal Security Service
+7-495-6063602 Presidential Executive Office
+7-495-9631102 P. B. Gannushkin Moscow City Clinical Psychiatric Hospital
+7-499-1582977 Moscow Aviation Institute
+7-903-5388412 "Pray to God" service
+375-225-449732 Babruisk hot line

Примечания

  1. Решение должно быть максимально практичным; в частности, недопустимо использовать для хранения ключей или значений типы существенно больших размерностей, чем это необходимо.
  2. Ключи в исходной последовательности могут повторяться; в отсортированной последовательности они должны сохранить свой относительный порядок.
  3. При тестировании гарантируется доступность оперативной памяти вдвое большей, чем исходная последовательность данных. Несмотря на это, необходимо обязательно учитывать возможную нехватку памяти и предусмотреть корректное завершение своей программы с соответствующим сообщением об ошибке.

Семплы

Первые тесты и ответы к ним.