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

      Создал вторую форму, сделав команду File-New-Form, и задал такие же свойства как и для главной формы.Фторая форма предназначена для отображения диаграммы сравнения двух способов сортировки (метод пузырька, метод простых вставок), а так же для сохранения результата сравнения двух методов сортировки в файл *txt. Для создания интерфейса второй формы использовал такие компоненты как: StatusBar, Timer (для отображения времени и даты в строке состояния),ImeageList ( для отображения иконок в главном меню), SaveDialog (для сохранения результата сравнения двух методов сортировки),Chart( для отображения диаграммы сравнения), ProgressBar( для отображения хода процесса сравнения).

      Создание третей формы нужно для отображения одного из разделов меню: О программе. На этой форме будут указываться версия продукта, и дополнительная информация о программе.Создав третюю форму присвоил ей такие значения:

      Закончил рабочее проектирование созданием справки и подключения файла *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 Метод  простых вставок

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

• Прост в реализации
• Эффективен на небольших наборах данных
• Эффективен на наборе данных которые уже частично отсортированы
• Это устойчивый алгоритм (не меняет порядок элеменов которые уже осотрированны)

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

   Алгоритм  метода простых вставок использует прием котрым пользуется игрок в карты при сортировки только что разданной колоды: очередная карта вставляется между уже упорядоченными ранее.

      Описания  метода простых вставок: файл подлежащий сортировке, в общем случае состоит  из элементов- записей, включающих информационную часть и ключи, по которым производятся упорядочение по возростанию. Поскольку информационная часть почти не влияет на процесс сортировки, предпологаем что файлы используемые в примерах, состоят только из элементов-ключей, а информационная часть записей. 
 
 
 
 
 
 
 
 
 

4 ВЫВОДЫ

      В ходе выполнения данного курсового  проекта были разработана программа  на языке высокого уровня Delphi 7. А также изучены возможности данного языка.

Систематизированы и закреплены практические навыки использования  ЭВМ, программного обеспечения, существующих средств обслуживания системных программистов, а также теоретические знания по основным разделам курса "Объектно-ориентированного программирования". Основное внимание уделено изучению современных методов защиты информации, способов проектирования приложений, объектно-ориентированному и системному программированию.

      При выполнении курсового проекта произведено  знакомство с реферативными журналами  и другими информационными источниками  по объектно-ориентированному и системному программированию с целью анализа состояния решаемой задачи.

      Получены  практические навыки работы в среде Delphi 7. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      

      

      ПРИЛОЖЕНИЕ  А

      Формы программы

На рисунке 1.1 изображено главное меню программы:

 

Рис 1.1 
 
 
 
 
 
 
 
 

На рисунке 1.2 показано  окно сравнения методов сортировки:

Рис. 1.2

На рис. 1.3 показано окно “О программе”

        
 
 
 
 
 
 
 
 
 
 
 

      

      

                  ПРИЛОЖЕНИЕ Б

Программа имеет возможность сохранять  обрабатываемые данные в файл     * txt.Сохранение производится в текстовый файл, который можно открыть с помощью любого текстового редактора.

      Также программа вводит исходный массив из файла * txt который создается пользователем самостоятельно в любом текстовом редакторе. При создании исходного массива нужно придерживаться следующих правил:

• Файл должен содержать только числовую информацию.
• Первая цифра должна соответствовать количеству элементов массива, и после этой цифры пользователь должен перейти на новую строку (Enter).
• После перехода на новую строку, пользователь вводит нужный ему одномерный массив и сохраняет его под любым именем в формате *txt.
• Если вышеуказанные пункты были выполнены, то программа откроет созданный вами файл для сортировки.

 
 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЕ В

Документация пользователя:

      Запуск программы осуществляется при открытии файла SortMass.exe, который находится на носители информации. При этом на экране появиться окно, в левой верхней части которого будет видна надпись “SortMass 1.0” – это имя программы. Ниже располагается меню, с помощью которого можно выполнить различные действия с данным приложением. При нажатии на пункте меню “Меню” выпадет, так называемое всплывающее меню, в котором находится пункты: получить массив, сохранить массив, сравнение методов, выход.

      Пункт  “получить массив” позволяет пользователю ввести массив из файла *txt, для его сортировки.

      Пункт “сохранить массив” позволяет сохранять отсортированный массив в файл *txt.

      При нажатии по пункту “сравнение методов”, открывается новое окно в котором указывается начальное количество элементов массива, конечное количество элементов массива, и шаг изменения, и по этим параметрам строится график сравнения двух методов сортировки.

      Следущй пункт “выход”, при выборе этого пункта программа закрывается.

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