Сазонова_20ВИ1. Сравнение и анализ алгоритмов сортировки массива прямым выбором
 Скачать 0.88 Mb.
|
Р | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
еферат| | | | | | ПГУ 09.03.02 - 03КР201.14 ПЗ | |||||
| | | | | | ||||||
| Изм. | Листт | № докум. | Подп. | Дата | ||||||
| Разраб. | Сазонова А.А. | | | «Сравнение и анализ алгоритмов сортировки массива прямым выбором» Пояснительная записка. | Лит. | Лист | Листов | |||
| Пров. | Самуйлов С.В. | | | | | | 4 | 34 | ||
| | | | | Группа 20ВИ1 | ||||||
| Н. контр. | | | | |||||||
| Утв. | | | | |||||||
Оглавление
Пояснительная записка 1
Реферат 4
Введение 7
1.Постановка задачи и анализ предметной области 8
1.1.Основные понятия и определения 8
1.2.Постановка задачи на разработку программы 9
1.3. Анализ требований 9
1.3.1.Требования к интерфейсу пользователя 9
1.3.2.Требования к структуре данных 10
1.3.3.Требования к программным средствам 11
2.Проектирование программы 14
2.1.Модель интерфейса 14
2.2.Проектирование структур данных 16
2.3.Структура программного обеспечения 17
3.Реализация программы 20
3.1.Кодирование 20
3.2.Диаграмма деятельности 20
4.Тестирование программы 22
4.1.Виды тестирования программных средств 22
4.2.Функциональное тестирование программы 24
Приложение А 30
Введение
Постановка задачи и анализ предметной области
Основные понятия и определения
Сортировка - это процесс упорядочивания наборов данных одного типа по возрастанию или убыванию значения какого-либо признака. Задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием.
Массив - это однородный, упорядоченный структурированный тип данных с прямым доступом к элементам. Элементы массива объединяются общим именем и занимают в компьютере определенную конечную область памяти. К любому элементу массива можно обратиться, указав имя массива и индекс элемента в массиве.
Алгоритм сортировки прямым выбором: при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.
Метод сортировки прямым выбором основан на следующих правилах:
Выбирается элемент с наименьшим ключом.
Он меняется местами с первым элементом a0.
Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.
Пример алгоритма сортировки прямым выбором изображен на рисунке 1.
Рисунок 1 – сортировка прямым выбором
Довольно простая модификация данной сортировки предусматривает поиск в одном цикле просмотра входного множества сразу и минимума, и максимума,и обмен их с первым и с последним элементами множества соответственно. Хотя итоговое количество сравнений и пересылок в этой модификации не уменьшается, достигается экономия на количестве итераций внешнего цикла.
Упорядоченная последовательность – значения элементов возрастают с увеличением номера элемента. Пример: 3, 4, 8, 9, 12.
Неупорядоченная последовательность – элементы не располагаются по возрастанию или убыванию с увеличением номера элемента. Пример: 9, 4, 11, 46.
Упорядоченная в обратном порядке последовательность – значения элементов убывают с увеличением номера элемента. Пример: 87, 59, 42, 13, 7.
Интерфейс — это набор инструментов, позволяющих пользователю взаимодействовать с операционной системой компьютера, мобильного устройства или других видов техники.
Структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.