Моделирование алгоритма работы сортировки элементов и метода поиска образца в упорядоченной информации

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ 

Государственное образовательное учреждение

высшего профессионального образования 

Кафедра  “Комплексная  защита  информационных  систем”

Специальность  090104  “Комплексная  защита  объектов  информатизации” 
 

КУРСОВОЙ  ПРОЕКТ 

по     МЕТОДАМ  ПРОГРАММИРОВАНИЯ  И 

ПРИКЛАДНЫМ  АЛГОРИТМАМ

  

“МОДЕЛИРОВАНИЕ  АЛГОРИТМА РАБОТЫ СОРТИРОВКИ ЭЛЕМЕНТОВ И МЕТОДА  ПОИСКА ОБРАЗЦА В УПОРЯДОЧЕННОЙ

ИНФОРМАЦИИ” 
 

СПОСОБ  СОРТИРОВКИ:  Посредством вставок и слияния        

                                                                        Название  способа

         МЕТОД  ПОИСКА: Бинарные атрибуты________________

                                           Название  метода 
 

Допустить к  защите 

Зав. кафедрой      КЗИС           Выполнил Клюев В.С._________              

                                                                                                 ^{(Ф.И.О студента )}                                                                 

проф. д.ф-м.н. В.П. Добрица  Студент   1^ого  курса гр.        ЗИ - 91____

    ^{(Должность, ученое звание, Ф.И.О.)                                                                           (Курс,  группа)}

                                                Работа защищена ___________________

                                                                                                                      ^{(Дата защиты)}

                                                  Оценка ____________________________ 

                                                  Руководитель доц. к.т.н. С.С.  Шевелев

                                                                                                                  ^{(Должность, ученое звание, Ф.И.О.)}     

                                             

Курск  2010 г.

1.Содержание

   1.Содержание курсового проекта……………………………….2

   2.Введение………………………………………………………..5

   3.Теоретическая часть……………………………………………6

         3.1.Сортировка посредством вставок и слияния…………..6

          3.2. Алгоритм поиска.Бинарные атрибуты…………………9

   4.Практическая часть……………………………………………12

      4.1. Блок схема алгоритма сортировки массива чисел посредством     

                  вставок и слияния простых вставок………………………………12

      4.2. Схема программы сортировки массива чисел посредством встевок

                   и слияния……………………………………………………………14

4.3. Блок схема алгоритма поиска через бинарные атрибуты

                заданного образца в упорядоченном массиве……………16

4.4. Схема программы поиска через бинарные атрибуты

                заданного образца в упорядоченном массиве……………18

      4.5. Описание алгоритма задания элементов массива……….20

       4.6. Текст программы, выполняющей сортировку массива

              символов способом простых вставок   …………………………..21

       4.7. Описание интерфейса программы……………………………33

      4.8. Таблицы результатов времени и скорости от количества   

               символов;…………………………………………………..34

       4.9. Графики зависимостей времени и скорости от количества

             чисел…………………………………..……………………36

    5.Заключение………………………………………………………39

   6.Список используемой литературы……………………………..40 

ЗАДАНИЕ: Упорядочить массив чисел в диапазоне от 1 до 100000 по убыванию и возрастанию методом сортировки посредством вставок и слияния.

ЦЕЛЬ  РАБОТЫ: разработать блок-схему алгоритма метода сортировки посредством вставок и слияния, создать схему программы, составить и протестировать программу на языке высокого уровня Delphi, получить результаты сортировки времени и скорости в зависимости от количества вводимых символов, построить графики зависимости в промежутках: [1 … 300], [300 … 5 000], [5 000 ... 10 000]

1) время  от количества символов в указанных  промежутках; 

2) скорость  от количества символов в указанных  промежутках.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Описание переменных и процедур: 

mas,mas2,bin_mas,bin_mas1 – массивы строк.

i, j, l, contr, elements – целые числа;

len,len1,len2 – хранение массива как строки.

p1,p2,p3 – счетчики элементов в сортировки слиянием.

time1, time2 – переменные для расчета времени.

i, j – счетчики циклов for.

bin_num – двоичный код искомого числа(алгоритм поиска).

flag, flag1 – переменные типа boolean;

s – строковая переменная.для вывода значений.

Button1.Click – процедура подготовки и заполнение массива случайными числами.

Button2.Click – процедура сортировки массива по возрастанию посредством вставок и слияния.

Button3.Click – процедура сортировки массива по убыванию посредством вставок и слияния.

Button4.Click – процедура поиска заданного образца в упорядоченном массиве через бинарные атрибуты .

IntToBin – процедура перевода элементов в двоичный код. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.  Введение

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

Современные вычислительные системы работают наиболее эффективно при упорядоченных данных. Сортировка информации — это процесс расстановки элементов в некотором порядке. Элементы размещаются следующем образом:

1) вычисления, которые требуют определенного  порядка расположения данных, упорядоченных по возрастанию или убыванию, могли выполняться эффективно,

    2)  результаты имели осмысленный вид,

3) последующие операции имели бы упорядоченные исходные данные.

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

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

       Поиск – нахождение нужного нам элемента в отсортированном массиве чисел. Одним из методов поиска является метод полного перебора. Хотя данный алгоритм работает не так быстро, как другие алгоритмы, он очень прост, что облегчает его написание и отладку. Данный алгоритм очень удобен для обработки совсем небольших списков.

   Так же можно рассмотреть двоичный поиск. Для того чтобы найти элемент, двоичный поиск несколько раз разбивает список на части, при этом в больших списках такой поиск выполняется намного быстрее, чем полный перебор. Идея, которая лежит в основе метода, достаточно проста, но реализовать ее гораздо сложнее.

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

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

3. Теоретическая часть
1. Сортировка посредством вставок и слияния

   Изящное обобщение изложенного выше метода принадлежит Лестеру Форду (мл.) (Lester Ford, Jr.) и Селмеру М. Джонсону (Selmer M. Johnson). Поскольку оно объединяет некоторые особенности двух способов сортировки (посредством слияний и посредством вставок), мы назовем этот метод сортировкой посредством вставок и слияния. Рассмотрим, например, сортировку 21 элемента. Начать можно со сравнений десяти пар ключей

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

аналогичную (5). Следующий шаг — вставить элемент  b₃ в последовательность {b₁,a₁,a₂}, а затем — b₂ в последовательность остальных элементов, меньших a_2. В результате приходим к конфигурации

Назовем верхние элементы главной цепочкой. Элемент b₅ можно вставить в главную цепочку за три сравнения (сравнив его сначала с c₄, затем с c₂ или c₆ и т. д.). После этого еще за три сравнения можно переместить в главную цепочку b₄ и получить

"Следующий  шаг решающий; ясно ли вам, что  делать дальше?" При помощи  всего четырех сравнений вставляем  b₁₁ (но не b₇) в главную цепочку. Далее элементы b₁₀, b₉, b₈, b₇ , b_б (именно в таком порядке) можно вставить в нужное место в главной цепочке не более чем за четыре сравнения каждый.

   Аккуратный  подсчет числа требуемых сравнений  показывает, что 21 элемент можно  рассортировать не более чем за 10 + 5(10) + 2 + 2 + 3+3+4+4+4+4+4 + 4 = 66 шагов. Поскольку