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

Автор работы: Пользователь скрыл имя, 22 Декабря 2013 в 15:21, курсовая работа

Краткое описание

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

Содержание

ВВЕДЕНИЕ………………………………………………………………… 5
1 ЛИТЕРАТУРНЫЙ ОБЗОР ПО АЛГОРИТМУ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ………………………………………………………........ 6
1.1 Краткие теоретические сведения об алгоритме прямое включение…. 6
1.2 Выбор материала для проведения теоретического исследования…. 6
2 ИССЛЕДОВАНИЕ АЛГОРИТМА СОРТИРОВКИ МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ……………………………………………………………….. ..7
2.1 Теоретическое исследование алгоритма прямое включение ………… 8
2.2 Практическое исследование алгоритма прямое включение ……….... 13
ЗАКЛЮЧЕНИЕ…………………………………………….…………………16
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ…………….……

Прикрепленные файлы: 1 файл

0361279_2C43E_issledovanie_sortirovki_metodom_pryamogo_vklyucheniya.doc

— 1.41 Мб (Скачать документ)

                                                     РЕФЕРАТ

 

 

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

 

В данной курсовой работе был рассмотрен метод сортировки прямым включением(вставкой). Все элементы условно разделяются на готовую последовательность 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 – это график зависимости sravnmax, а кривая 2 – это график зависимости sravnmin.

 

 

     

  

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

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

 

 

 

 

 

 

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

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

 

 

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

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

 

 

sravnср теор(n)=(sravnmax(n) + sravnmin(n))/2                    (1.5)

 

         peremср теор=(peremmax(n)+ peremmin(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 Практическое исследование алгоритма прямого включения.

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

Информация о работе Метод сортировки прямым включением