Реферат: Задачи: Создать и реализовать алгоритм построения массива данных, содержащего информацию со случайными ключами. Реализовать предложенные алгоритмы внутренней сортировки

Методы программирования


Задание. Реализация методов внутренней сортировки в виде динамической библиотеки.


Под динамической библиотекой понимается библиотека функций, выполненной в виде отдельного откомпилированного модуля DLL, который присоединяется к исполняемому файлу во время его исполнения.

Задачи:

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

Реализовать предложенные алгоритмы внутренней сортировки.

Скомпоновать алгоритмы сортировки в виде DLL.

Реализовать графическую оболочку для тестирования созданных алгоритмов сортировки.

Комментарии:

Формируемый массив данных должен содержать произвольную информацию в поле данных (например, текст) и ключи для сортировки. Ключ – это число, имеющее тип беззнакового целого. При создании массива ключи должны иметь случайные значения с равномерным распределением на интервале от 1 до N, где N – число, задаваемое пользователем.

Размер массива также задается пользователем, но с условием, что его размер не превышает половины всей свободной памяти компьютера.

Алгоритмы сортировки должны быть реализованы согласно [1]. Методы сортировки будут выбраны из списка:

карманная сортировка с двумя массивами;

сортировка простым выбором;

пузырьковая сортировка;

карманная сортировка в исходном массиве;

шейкер-сортировка;

метод подсчета сравнений;

метод простых вставок;

метод двухпутевых вставок;

метод бинарных вставок;

сортировка простым двухпутевым слиянием;

сортировка квадратичным выбором;

поразрядная распределяющая сортировка, начиная со старших разрядов;

сортировка естественным двухпутевым слиянием;

метод Шелла;

поразрядная распределяющая сортировка, начиная с младших разрядов;

пирамидальная сортировка;

поразрядная обменная сортировка;

быстрая сортировка Хоара (сортировка с разделением);

метод Бетчера;

сортировка квадратичным выбором;

сортировка кубическим выбором.

Алгоритмы должны быть реализованы в виде функций, которые в качестве исходных параметров принимают: указатель на первый элемент массива и размер массива. Возвращаемый результат – указатель на отсортированный массив.

Все реализованные алгоритмы должны быть скомпонованы в виде библиотеки DLL, название каждой функции должно быть созвучно с названием метода сортировки.

Графическая оболочка должна обеспечивать ввод необходимой информации для создания массива данных, его просмотра и запуска необходимых методов сортировки.

Оболочка как исполняемый файл использует методы сортировки, осуществляя доступ к функциям DLL.



[1] Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск.