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

Вид материала

Документы

Подобный материал:

• Общее задание Последовательность выполнения работы Реализовать алгоритмы сортировки,, 114kb.
• Календарный план работы Дата проведения консультации Этап выполнения работы Отметка, 14.84kb.
• Алгоритмы сортировки, 18.78kb.
• Удк 004. 021+004. 81 Алгоритмы построения маршрута на карте по параметрам, 88.51kb.
• Закон трихотомии, 527.85kb.
• Алгоритм и программа поиска минимального и максимального элементов в массиве. Задача, 17.73kb.
• Реализовать функцию протокола ModBus $03 для чтения из адресного пространства данных., 125.1kb.
• Программа курса Алгоритмы программирования, 47.59kb.
• Алгоритмы сортировки, 19.5kb.
• Задачи деятельности: Реализовать экспертизу эффективности внедрения и мониторинговое, 145.58kb.

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


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


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

Задачи:

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

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

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

1. карманная сортировка с двумя массивами;
   
2. сортировка простым выбором;
   
3. пузырьковая сортировка;
   
4. карманная сортировка в исходном массиве;
   
5. шейкер-сортировка;
   
6. метод подсчета сравнений;
   
7. метод простых вставок;
   
8. метод двухпутевых вставок;
   
9. метод бинарных вставок;
   
10. сортировка простым двухпутевым слиянием;
    
11. сортировка квадратичным выбором;
    
12. поразрядная распределяющая сортировка, начиная со старших разрядов;
    
13. сортировка естественным двухпутевым слиянием;
    
14. метод Шелла;
    
15. поразрядная распределяющая сортировка, начиная с младших разрядов;
    
16. пирамидальная сортировка;
    
17. поразрядная обменная сортировка;
    
18. быстрая сортировка Хоара (сортировка с разделением);
    
19. метод Бетчера;
    
20. сортировка квадратичным выбором;
    
21. сортировка кубическим выбором.
    

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

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