Лабораторная работа №2: Сортировка и поиск

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

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

• Для каждого вызова процедуры сортировки необходимо печатать исходное состояние таблицы и результаты сортировки. После выполнения сортировки программа должна вводить ключи и для каждого из них выполнять поиск в упорядоченной таблице с помощью процедуры двоичного поиска и печатать найденные элементы, если они присутствуют в таблице.

• В процессе отладки и тестирования рекомендуется использовать команды обработки текстовых файлов ОС UNIX и переадресацию ввода-вывода. Тестовые данные необходимо заранее поместить в текстовые файлы.

Выполнен вариант:

• Сортировка №8: древесная сортировка с просеиванием (heap sort)
• Структура №6: вещественный ключ, хранение ключей и данных отдельно

Программа находится в файле main.c

Сборка

gcc main.c -o main

Запуск

./main

или

./main < test.txt #С тестами

После запуска программа:

1. Просит ввести число элементов (не меньше 16).
2. Считывает таблицу записей (вещественный ключ + строковые данные).
3. Проверяет сортировку в трех случаях:
   • уже упорядоченная таблица;
   • обратный порядок;
   • неупорядоченная таблица.
4. Для каждого случая печатает таблицу до и после сортировки.
5. Выполняет двоичный поиск по вещественным ключам в отсортированной таблице.