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

Первой своей форме я уже присвоил выше показанные свойства. Теперь на форме 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) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в массиве и их предварительной упорядоченности.
Рассмотрим алгоритмы наиболее распространенных методов внутренней сортировки ( упорядочение выполняется по возрастанию значений ключа ).

5.2.Метод "Пузырька".

При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода массива сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен, то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами. После первого прохода запись с наибольшим ключом будет находиться на n - й позиции массива. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1, n-2, ... , 2 соответственно, в результате чего будет сформирована отсортированная таблица. После каждого прохода через массив может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что массив уже отсортирован и дальнейших проходов не требуется. Кроме того, можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемый массив.
Характеристики сортировки методом "пузырька" в худшем случае составляют n(n-1)/2 сравнений и n(n-1)/2 перестановок (худшим считается случай,когда элементы наиболее удалены от своих конечных позиций). Среднее число сравнений и перестановок имеет порядок n**2 . Сортировка пузырьковым методом использует метод обменной сортировки.

Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой когда каждый пузырек находит свой собственный уровень.

Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

5.3 Метод простых вставок

Сортировка вставками - простой алгоритм сортировки. Этот метод сортировки менее эффективен чем более сложные алгоритмы ( такие как быстрая сортировка), но у него есть ряд преймушеств:

· Прост в реализации

· Эффективен на небольших наборах данных

· Эффективен на наборе данных которые уже частично отсортированы

· Это устойчивый алгоритм (не меняет порядок элеменов которые уже осотрированны)

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