Разработка и программирование алгоритма сортировки методом перестановки данных. Выбор структур данных для решения задачи. Логическое и физическое проектирование программного обеспечения. Проектирование интерфейса, кодирование и тестирование программы.
Аннотация к работе
Алгоритм сортировки используется в практически любой программной системе. Поиск элемента в последовательности отсортированных данных занимает время, пропорциональное логарифму количеству элементов в последовательности, а поиск элемента в последовательности не отсортированных данных занимает время, пропорциональное количеству элементов в последовательности, то есть намного больше. Однако любой алгоритм сортировки можно разбить на три основные части: · Сравнение, определяющее упорядоченность пары элементов;В соответствии с целями данного курсового проекта, возможно начать проектирование и анализ требуемых для проекта программ. Построить блок-схемы, наглядно отображающие принцип работы алгоритмов сортировок методами быстрой сортировки, сортировки Шелла, сортировки слиянием.В данной работе необходимо разработать программу, реализующую следующие задачи: интерфейс кодирование программа алгоритм · Формирование одномерного динамического массива Mass c количеством элементов Kol, задаваемым пользователем, случайным образом. При написании программ для реализации сортировок массивов был использован язык программирования С .Массив Mass Int Переменная Kol,i long Переменная SLSORTTIME Int Переменная SHELLSORTTIME Int Переменная QSORTTIME IntПри сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местами с предпоследним (n-1)м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте. При сортировке данных выполняется обмен содержимого переменных. Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент.MAINUNIT.cpp SIMPLECHOOSE *mass , int Kol Сортировка Массива mass с количеством элементов Kol методом простого выбора. MAINUNIT.cpp INSERTIONSORT *mass , int Kol Сортировка Массива mass с количеством элементов Kol методом простых вставок.В качестве интерфейса программы будет использованы две визуальные формы Windows. Это наиболее наглядный и интуитивно понятный способ представления информации, в отличии от консольных приложения имеющий гораздо больший потенциал визуального оформления.Реализация алгоритма сортировки методом простого выбора. // Выполняем сортировку for(i=Kol-1;i>0;i-) //Устанавливаем начальное значение и номер // Ищем максимальный элемент for(j=0;j<=i-1;j ) Mass[j]= Mass[n];1000 элементов массива TFORM1::SIMPLECHOOSE Сохранение массива, отсортированного методом простого выбора в файл и подсчет времени выполнения 1000 элементов массива TFORM1::INSERTIONSORT Сохранение массива, отсортированного методом простых вставок в файл и подсчет времени выполнения 1000 элементов массива TFORM1::COUNTCOMPARES Сохранение массива, отсортированного методом подсчета сравнений в файл и подсчет времени выполнения 10000 элементов MAINUNIT.cpp Подсчет времени работы каждого метода сортировки и построение гистограммы. Дата, Время Тестируемый модуль или подпрограмма Кто проводил тестирование Описание теста Результаты тестированияБыл сделан вывод, что сортировка методом простых вставок более эффективна в целом, чем остальные методы.1. Техническое заданиеПрограмма создана для сравнения по скорости работы 3-х способов сортировки данных в одномерном динамическом массиве: простого выбора, простых вставок, подсчета сравнений. Программа должна обеспечивать возможность сортировки данных разными способами, сохранение отсортированных массивов в файл, вывод гистограммы для сравнения скорости работы алгоритмов. В программе должны быть просчитаны ошибочные комбинации ввода данных. Климатические условия эксплуатации, при которых должны обеспечиваться заданные характеристики, должны удовлетворять требованиям, предъявляемым к техническим средствам в части условий их эксплуатации В состав технических средств должен входить ІВМ-совместимый персональный компьютер (ПЭВМ), процессор Pentium-2.0Hz, оперативную память объемом не менее 512 мб, операционную систему Цindows xp.Порядок контроля и приемки Наименование контрольного этапа выполнения курсовой работы Сроки контроля Результат выполнения Отметка о приемке результата контрольного этапа Описание работы алгоритмов 13.10.14Алгоритм метода простых вставокВнешний вид программы представлен на Рис.1 Пользователь вводит в поле «Количество элементов» размер массива и нажимает кнопку «Сортировать». Если мы вводим число меньше 10000, то получаем сообщение о неправильности ввода Рис 2 Если мы вводим в поле «Количество элементов» символы не являюшиеся числами или вещественное число, то у нас выйдет следующее сообщение: Рис.
План
Оглавление
Введение
1. Изучение и описание предметной области
2. Постановка задачи
3. Выбор структур данных для решения поставленной задачи
4. Логическое проектирование
5. Физическое проектирование программного обеспечения