Иследование методов сортировки Метод пузырька и Метод простых вставок

СОДЕРЖАНИЕ
1. Введение……………………………………………………...4
2. Постановка задачи……………………………………………6
3. Рабочее проектирование……………………………………..8
4. Методы сортировок…………………………………………..12
4.1. Общее
4.2. Метод "Пузырька"
4.3. Метод "Простых вставок.
Выводы……………………………………………………….16
Приложения
Приложение А………………………………………………...17
Приложение Б………………………………………………….19
Приложение В………………………………………………….20
Приложение Г………………………………………………….22

ВВЕДЕНИЕ
Объектно-ориентированное программирование предполагает быструю разработку приложений с использованием визуальных компонентов. По сравнению с традиционными способами программирования ООП обладает рядом преимуществ. Главное из них заключается в том, что эта концепция в наибольшей степени соответствует внутренней логике функционирования операционной системы (ОС) Windows. Программа, состоящая из отдельных объектов, отлично приспособлена к реагированию на события, происходящие в ОС. К другим преимуществам ООП можно отнести большую надежность кода и возможность повторного использования отработанных объектов.
Столпом объектно-ориентированного программирования считается наследование, оно даёт возможность порождать новые классы, не описывая лишний код.
К недостаткам объектно-ориентированного программирования можно отнести сравнительно большой объём приложений, написанных на языке высокого уровня.
Бурное развитие вычислительной техники, потребность в эффективных средствах разработки программного обеспечения привели к появлению систем программирования, ориентированных на так называемую "быструю разработку", среди которых можно выделить Borland Delphi и MicrosoftVisualBasic. В основе систем быстрой разработки (RAD-систем, RapidApplicationDevelopment — среда быстрой разработки приложений) лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть рутинной работы, оставляя программисту работу по конструированию диалоговых окон и функций обработки событий. Производительность программиста при использовании RAD-систем - фантастическая!
Delphi — это среда быстрой разработки, в которой в качестве языка программирования используется язык Delphi. Язык Delphi — строго типизированный объектно-ориентированный язык, в основе которого лежит хорошо знакомый программистам ObjectPascal. Delphi продолжила серию Паскаль - ориентированных средств программирования и, по моему глубокому убеждению, является наиболее удобным инструментом для Windows-программирования.
Цель программирования может быть сформулирована так: научить программировать в среде Delphi, т. е. создавать законченные программы различного назначения: от простых однооконных приложений до вполне профессиональных программ работы с базами данных.
Объектно-ориентированное проектирование претендует на роль последнего слова в методологии проектирования, однако оно представляет собой сплав многих лучших идей в области создания сложных систем. Такие системы уже созданы в различной предметной области, а сам переход успешно использован как для задач в несколько сот строк кода, так и в 1 – 10 миллионов строк. Пока нет экспериментальных (практических) доказательств, что данная методология позволит реализовать системы объемом в десятки миллионов строк кода. Можно полагать, что развитие объектно-ориентированного проектирования приведет к тому, что будут созданы системы невообразимой сложности.
Действительно, требования к уровню программных систем резко возрастают. Современные возможности аппаратных средств и общественная потребность в компьютеризации все более и более требуют расширения сферы автоматизации. Потенциальные возможности объектно-ориентированного проектирования, включая процедурные вопросы и документирование, дают свободу энергии человека и позволяют преодолеть препятствия на пути создания сложных систем.
Delphi — чрезвычайно мощная система разработки прикладных программ для Windows. Она все увереннее завоевывает ведущие позиции в нашей стране, как среди профессиональных программистов, так и среди людей, никогда профессионально программированием не занимавшихся.
Профессионалы используют Delphi для построения сложных приложений с распределенными базами данных и для многих других целей. Специалисты самых разных специальностей (не программисты) создают с помощью Delphi небольшие прикладные программы для решения своих профессиональных задач и радуются, что, не владея всерьез программированием, могут создавать интерфейс, неотличимый от привычного интерфейса Windows.
Студенты (не программисты) выполняют с помощью Delphi свои курсовые и дипломные проекты. Сейчас уже есть даже средние школы, в которых начинают знакомить с работой в среде Delphi.
Научиться программировать можно только программируя, решая конкретные задачи. При этом достигнутые в программировании успехи в значительной степени зависят от опыта. Поэтому, чтобы получить максимальную пользу от программирования, вы должны работать с ним активно. Не занимайтесь просто чтением примеров, реализуйте их с помощью вашего компьютера. Не бойтесь экспериментировать — вносите изменения в программы. Чем больше вы сделаете самостоятельно, тем большему вы научитесь!!!

1 ПОСТАНОВКА ЗАДАЧИ
Целью выполнения курсового проектирования было реализовать алгоритмы сортировки одномерных массивов (метод пузырька и метод простых вставок), и исследование каждого метода сортировки массива.
Приложение должно иметь возможность сортировки массива (методом пузырька, методом простых вставок), одномерный массив для сортировки должен вводится из файла *txt, а так же после сортировки сохранятся в файл *txt. Отсортированный массив должен сравниваться с исходным и отображаться в виде диаграммы.
А также программа после сортировки должна сравнивать методы сортировки (метод пузырька и метод простых вставок), и показывать пользователю, какой из двух методов сортирует массив быстрее. Результат исследование двух массивов должен сохранятся в файл *txt. Структура интерфейса должна быть максимально понятна для пользователя.

2 РАБОЧЕЕ ПРОЕКТИРОВАНИЕ
Данную задачу я буду реализовывать в Delphi7.Для этого я запустил программу Delphi и выполнил команду: File-New-Application. В верхней части нашего окна мы видим полосу главного меню. Ниже полосы главного меню расположены две инструментальные панели. Левая панель содержит два ряда быстрых кнопок, дублирующих некоторые наиболее часто используемые команды меню. Правая панель содержит палитру компонентов библиотеки визуальных компонентов. Правее полосы главного меню в Delphi7 размещена еще одна небольшая инструментальная панель, содержащая выпадающий список и две быстрые кнопки.
В основном поле окна мы можем увидеть слева два окна: вверху -Дерево Объектов(ObjectTreeView), под ним – Инспектор Объектов(ObjectInspector). Окно Дерева Объектов отображает иерархическую связь компонентов и объектов нашего приложения. Инспектор Объектов это основной инструмент, с помощью которого можно задавать свойства компонентов и обработчики событий. Правее этих окон мы можем видеть окно пустой формы, готовой для переноса на нее компонентов, а под ним расположено окно Редактора Кодов.
Для этого приложения я создам три формы которые свяжу между собой. Для Form1(она будет нашей главной формой) установим такие значения:
Свойство Значение Коментарий
Caption SortMassiv 1.0 Строка текста, идентифицирующая компонент для пользователя
Height 576 Высота формы
Width 836 Ширина формы
Position poMainFormCenter Позиция формы при запуске программы
Эта форма будет содержать поля ввода и вывода отсортированного массива, а так же на ней будет располагаться кнопки для сохранения отсортированного массива, а так же компонент для отображения графа.
Первой своей форме я уже присвоил выше показанные свойства. Теперь на форме SortMass 1.0 нужно сделать меню. В Delphi имеется два компонента, представляющие меню: MainMenu - главное меню, и PopupMenu -всплывающее меню или контекстное меню. Оба эти компонента расположены на вкладке Standard . Для своего приложения меню я буду использовать MainMenu.Для этого я его расположил на форме и двойным щелчком мыши по компоненту открыл конструктор меню и создал там три раздела меню и для каждого из них сделал свои подразделы:
· Меню→ Получить массив→ Сохранить массив→ Сравнение методов;
· О программе;
· Справка;
Далее я приступил к созданию «рабочего поля» программы, разместил на форму два компонента Panel , и разделил их между собой компонентом Splitter этот компонент позволяет перемещать границы, разделяющие различные панели, изменяя их относительные размеры. На одну из панелей разместил два компонента Label для отображения исходного, и отсортированного массива. Далее на одну панель расположил компонет Chart – этот компонент позволяет строить различные диаграммы, и графики. Для Chart установим такие значения:
Свойство Значение Коментарий
TChartSeriesList
Исходный,
Отсортированный
Строка в которой указываются серии для отображения их на графике
Title Иллюстрация сортировки Определяет заголовок формы
Эта форма будет содержать поля ввода и вывода отсортированного массива, а так же на ней будет располагаться кнопки для сохранения отсортированного массива, а так же компонент для отображения графа.
Первой своей форме я уже присвоил выше показанные свойства. Теперь на форме SortMass 1.0 нужно сделать меню. В Delphi имеется два компонента, представляющие меню: MainMenu - главное меню, и PopupMenu -всплывающее меню или контекстное меню. Оба эти компонента расположены на вкладке Standard . Для своего приложения меню я буду использовать MainMenu.Для этого я его расположил на форме и двойным щелчком мыши по компоненту открыл конструктор меню и создал там три раздела меню и для каждого из них сделал свои подразделы:
· Меню→ Получить массив→ Сохранить массив→ Сравнение методов;
· О программе;
· Справка;
Далее я приступил к созданию «рабочего поля» программы, разместил на форму два компонента Panel , и разделил их между собой компонентом Splitter этот компонент позволяет перемещать границы, разделяющие различные панели, изменяя их относительные размеры. На одну из панелей разместил два компонента Label для отображения исходного, и отсортированного массива. Далее на одну панель расположил компонет Chart – этот компонент позволяет строить различные диаграммы, и графики. Для Chart установим такие значения:
Свойство Значение Коментарий
TChartSeriesList
Исходный,
Отсортированный
Строка в которой указываются серии для отображения их на графике
Title Иллюстрация сортировки Определяет заголовок формы
При двойном щелчке по компоненту Chart вызываем конструктор диаграмм, в котором можно выбрать из стандартных типов диаграмм нужный мне тип. Также в этом конструкторе на вкладкеSeries выберу нужный цвет для каждой из созданных серий.
Далее поставил на форму кнопки при нажатии на которых будут выполнятся такие действия как : сохранение отсортированного массива, сравнение методов сортировки массивов, открытия массива из файла *txt, отчистка полей для повторной сортировки. Также для создания интерфейса программы использовал такие компоненты как : StatusBar , Timer (для отображения времени и даты в строке состояния),ImeageList ( для отображения иконок в главном меню), SaveDialog (для сохранения отсортированного массива), OpenDialog (для открытия исходного массива), GroupBox , RadioGroup .
Создал вторую форму, сделав команду File-New-Form, и задал такие же свойства как и для главной формы.Фторая форма предназначена для отображения диаграммы сравнения двух способов сортировки (метод пузырька, метод простых вставок), а так же для сохранения результата сравнения двух методов сортировки в файл *txt. Для создания интерфейса второй формы использовал такие компоненты как: StatusBar , Timer (для отображения времени и даты в строке состояния),ImeageList ( для отображения иконок в главном меню), SaveDialog (для сохранения результата сравнения двух методов сортировки),Chart ( для отображения диаграммы сравнения), ProgressBar( для отображения хода процесса сравнения).
Создание третей формы нужно для отображения одного из разделов меню: О программе. На этой форме будут указываться версия продукта, и дополнительная информация о программе.Создав третюю форму присвоил ей такие значения:
Свойство Значение Коментарий
Caption О программе Строка текста, идентифицирующая компонент для пользователя
Height 211 Высота формы
Width 308 Ширина формы
Position poMainFormCenter Позиция формы при запуске программы
biMinimaze false Окно не сворачивается
biMaximaze false false Окно не разворачивается
BorderStyle bsSizeable Нельзя поменять размер окна
Закончил рабочее проектирование созданием справки и подключения файла *hlpк разработанному приложению.
3 МЕТОДЫ СОРТИРОВОК
5.1Общее.
Основными операциями, выполняемыми над массивами, являются упорядочение (сортировка) записей и поиск в массиве записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей массива в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если массив целиком помещается в оперативной памяти ЭВМ, то его упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются:
С - количество операций сравнения пар ключей,
Р - число перестановок элементов ,
S - резерв памяти.
Среднее количество операций сравнения зависит от метода сортировки и при рациональном выборе метода достигает некоторого минимума, зависящего от n - размера массива (размер массива - количество содержащихся в нём записей). Методы внутренней сортировки можно разделить на две группы:
- методы, не требующие резерва памяти;
- методы, требующие резерва памяти.
К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений.
Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в массиве и их предварительной упорядоченности.
Рассмотрим алгоритмы наиболее распространенных методов внутренней сортировки ( упорядочение выполняется по возрастанию значений ключа ).

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию