Задание №9 к курсовому проекту

Сортировки и поиск

Задание

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

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

На первой строке находится число M, указывающее количество записей таблице. На следующих M строках находятся пары ключ-значение, разделенные знаком табуляции. Типы ключа и значения зависят от варианта задания. Далее до конца файла находятся ключи, которые нужно искать в таблице.

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

Таблица, состоящая из тех же строк, что и входная, но расположенных в отстортированном порядке. Для каждого ключа, который нужно было найти в таблице вывести соответствующие значения, разделенные знаком табуляции или "Not found", если такого ключа в таблице нет.

Варианты сортировок

  1. Линейный выбор с обменом.
  2. Линейный выбор с подсчетом.
  3. Метод пузырька.
  4. Шейкер-сортировка.
  5. Метод простой вставки.
  6. Метод двоичной вставки.
  7. Пирамидальная сортировка с просеиванием.
  8. Метод Шелла.
  9. Простое двухпоточное слияние.
  10. Быстрая сортировка Хоара (рекурсивный вариант).
  11. Быстрая сортировка Хоара (нерекурсивный вариант).
  12. Четно-нечетная сортировка (парный обмен, основанный на методе пузырька).
  13. Прямое слияние.
  14. Естественное слияние.

Варианты типов ключей (или значений)

  1. Строки переменной длины (макс. размер 256 байт).
  2. Целые числа.
  3. Вещественные числа (с двумя знаками после запятой).
  4. Комплексные числа (задаются парой целых чисел, записанных через пробел, в качестве функции, задающей отношение порядка взять модуль числа).