Метод сортировки прямым включением

                                                     РЕФЕРАТ

 

 

СОРТИРОВКА, ПРЯМОЕ ВКЛЮЧЕНИЕ, ЧИСЛО СРАВНЕНИЙ, СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ГРАФИК ЗАВИСИМОСТИ, МАКСИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ, МИНИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ,

 

В данной курсовой работе был рассмотрен метод сортировки прямым включением(вставкой). Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i- элемент входной последовательности и вставляем его нанужное место в готовую.

Были проведены два эксперимента с пятью массивами разной длинны, в которых проводился поиск десяти разных ключей по десять раз в каждом массиве. Эксперименты позволили увидеть  работу метода и рассчитать среднее, максимальное и минимальное количество сравнений при проведении поиска.

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

 

 

                                                   СОДЕРЖАНИЕ

 

 

 

ВВЕДЕНИЕ…………………………………………………………………     5 

1 ЛИТЕРАТУРНЫЙ ОБЗОР  ПО АЛГОРИТМУ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ………………………………………………………........    6

1.1  Краткие теоретические сведения об алгоритме прямое включение…. 6

  1.2  Выбор материала для проведения теоретического исследования….    6

2 ИССЛЕДОВАНИЕ АЛГОРИТМА СОРТИРОВКИ МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ……………………………………………………………….. ..7 

2.1 Теоретическое исследование  алгоритма прямое включение ………… 8

2.2 Практическое исследование  алгоритма прямое включение ………....  13 

ЗАКЛЮЧЕНИЕ…………………………………………….…………………16

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ…………….……………… .17

ПРИЛОЖЕНИЕ E – Код программы №1………………………………….18

ПРИЛОЖЕНИЕ F – Код программы №2………………………………….23

 

ВВЕДЕНИЕ

 

 

Целью курсовой работы является закрепление полученных знаний во втором семестре, где мною были изучены  основные структуры данных и алгоритмы, которые работают с ними. Среди этих алгоритмов широко известен метод прямое включение, который и будет исследован в курсовой работе. Исследования будут проведены теоретическими и практическими методами, на основании которых будут составлены таблицы и графики зависимостей 
1. ЛИТЕРАТУРНЫЙ ОБЗОР ПО АЛГОРИТМУ

ПРЯМОГО ВКЛЮЧЕНИЯ.

1.1 Краткие  теоретические сведения об алгоритме прямое включение.

В одной из книг [1, 442-444] рассказывается о принципе работы алгоритма бинарного поиска в массиве. Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива.

Для поиска места i-ro элемента каждый раз потребуется выполнить от 1 до i-1 операций сравнения, т.е. в среднем i/2 операций сравнения. Значение i изменяется от 2 до п, т.е. выполняется п-1 проход, в каждом из которых происходит в среднем от 1 до п/2 сравнений. Таким образом, суммарно в среднем для решения задачи требуется выполнить (n-l)(n/2 + 1)/2 = (n2 + п - 2)1 А операций сравнения. Откуда вычислительная сложность метода в среднем также равна Оср(п2), хотя время выполнения примерно в два раза меньше, чем у предыдущего метода. Интересно, что в данном случае вычислительная сложность зависит от исходного расположения элементов массива.

 

1. Выбор материала для проведения теоретического исследования.

    Произведя литературный обзор можно сделать следующий вывод, что довольно полная информация об алгоритме прямое включение содержится в литературном источнике [2,  66-69, 493-498,].

Будем использовать следующие формулы зависимости максимального и минимального числа сравнений от числа элементов в массиве, которые были там [2,  66-69, 493-498,] приведены:

формула зависимости максимального числа сравнений от числа элементов в массиве из N элементов sravnmax =  ( n^2 + n ) * / 2 - 1            (1.1);

     (n – 1) -формула зависимости минимального числа сравнений от числа элементов в массиве из N элементов.

        2. ИССЛЕДОВАНИЕ АЛГОРИТМА ПРЯМОЕ ВКЛЮЧЕНИЕ

 

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

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

Так как в задании  на курсовой проект указываются массивы для исследования от 10 до 100 элементов, положим, что N – максимальное число элементов в массивах равно  10<=N<=100.

 

 

 

 

 

 

 

 

 

 

 

 

2.1 Теоретическое  исследование алгоритма прямое включение

 

В литературе [2,  66-69, 493-498,] были предложены следующие зависимости числа сравнений от числа элементов в массиве :

формула зависимости  максимального числа сравнений  от числа элементов  в массиве;                           ( n^2 + n ) * / 2 - 1                               (1.1)

 

формула зависимости минимального числа сравнений от числа элементов     в массиве;                                       n - 1                                               (1.2)

 

формула зависимости  максимального числа перемещений  от числа элементов в массиве;                 ( n^2 + 3 * n - 4 ) / 2                                (1.3)

 

формула зависимости  минимального числа перемещений  от числа элементов   в массиве.                                  2 * (n - 1)                                     (1.4)

     Построим по формулам (2.1) – (2.2) графики зависимостей максимального и минимального числа сравнений для бинарного поиска.

Чтобы построить графики зависимостей максимального и минимального числа сравнений для метода прямого включения, мы возьмем десять произвольных массивов с числом элементов от 10 до 100 и подставим их значения в формулы (1.2) и (1.3), результаты запишем в таблицу(1).

 

Таблица 1 

Результаты, полученные при практическом исследовании

 

N	10	20	30	40	50	60	70	80	90	100
sravnmin	9	19	29	39	49	59	69	79	89	99
sravnmах	54	209	464	819	1274	1829	2484	3239	4094	5049
peremmin	18	38	58	78	98	118	138	158	178	198
peremmax	63	228	493	858	1323	1888	2553	3318	4183	5148

      

    Таблица 1 - зависимости максимального и минимального числа сравнений для алгоритма прямое включение. Где N – количество элементов в массиве, sravnmax – максимальное число сравнений , sravnmin – минимальное число сравнений соединяют линиями, а полученная в результате кривая – это график зависимости среднего числа сравнений от числа элементов массива.

Так на рисунке 2.1 была получена теоретическая плоскость, в которой  могут находиться значения числа  сравнений в зависимости от числа  элементов в массиве, где кривая 1 – это график зависимости sravn_max, а кривая 2 – это график зависимости sravn_min.

 

 

     

  

 Рис. 2.1 -  Теоретическая плоскость нахождения числа

                    сравнений в зависимости от  кол-ва элементов.

 

 

 

 

 

 

Рис. 2.2 -  Теоретическая плоскость нахождения числа

                    перемещений в зависимости от кол-ва элементов.

 

 

Так на рисунке 2.2 была получена теоретическая плоскость, в которой могут находиться значения числа сравнений в зависимости от числа элементов в массиве, где кривая 1 – это график зависимости perem_max, а кривая 2 – это график зависимости perem_min.

Теперь, когда были получены теоретические плоскости, можно  построить графики зависимостей среднего значения числа сравнений и перемещений от числа элементов в массиве (рис. 2.3, 2.4). Для этого используем формулы:

 

 

sravn_{ср теор}(n)=(sravn_max(n) + sravn_min(n))/2                    (1.5)

 

         perem_{ср теор}=(perem_max(n)+ perem_min(n))/2.                  (1.6)

 

 

 

 

Таблица 2

                  Средние значения числа сравнений  из табл. 1

 

N	10	20	30	40	50	60	70	80	90	100
sravnmin	9	19	29	39	49	59	69	79	89	99
sravnmах	54	209	464	819	1274	1829	2484	3239	4094	5049
sravnсртеор	31,5	114	246,5	429	661,5	944	1276,5	1659	2091,5	2574

 

 

 

 

 

Таблица 3  

                       Средние значения числа перемещений из табл. 1

                         

N	10	20	30	40	50	60	70	80	90	100
peremmin	18	38	58	78	98	118	138	158	178	198
peremmax	63	228	493	858	1323	1888	2553	3318	4183	5148
peremсртеор	40,5	133	275,5	468	710,5	1003	1345,5	1738	2180,5	2673

 

                                      

 

Необходимо проверить  следующее. Располагается ли график зависимостей sravn_сртеор(N) и peremсртеор(N) в теоретической плоскости, в которой могут находиться значения числа сравнений в зависимости от числа элементов в массиве. Для этого совместим графики зависимостей рисунков 2.1 и 2.2 с sravn_сртеор(N) и peremсртеор(N ) из таблиц 2 и 3. Эти совмещения приведём ниже (рис. 2.3 и 2.4).

 

 

 

 

 

 

      Рис.  2.3 – Среднее значение числа сравнений попадает

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

 

 

                                                            

             Рис.  2.4 – Среднее значение числа перемещений попадает

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

 

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

 

2.2 Практическое исследование алгоритма прямого включения.

Для того, чтобы провести практическое исследование данного алгоритма составим программу, которая будет определять точки sravn_cpпр и peremсрпр в зависимости от значения числа элементов используемого массива и его упорядоченности(см. ПРИЛОЖЕНИЕ E). Эксперимент проведем десять раз, в каждом массиве поиск будет проводиться по десять раз, для нахождения sravn_cpпр(n) и peremсрпр(n).Полученные результаты сведём в таблицу 4 и 5. Далее по данным таблиц 4 и 5 построим точки на графике (рис. 2.5 ), соединив которые получим графики зависимостей среднего числа сравнений и перемещений от числа сортируемых элементов массива, sravn_cpпр(n) и peremсрпр(n), полученные практическим способом.