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

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

РЕФЕРАТ

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

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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

ВВЕДЕНИЕ

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

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 Выбор материала для проведения теоретического исследования

Произведя литературный обзор можно сделать следующий вывод, что довольно полная информация об алгоритме прямое включение содержится в литературном источнике [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

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

Таблица 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

Таблица 3

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

Необходимо проверить следующее. Располагается ли график зависимостей 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), полученные практическим способом.

Таблица 4

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

Таблица 5

Результаты, полученные при трёх практических исследованиях (упорядоченные, обратно упорядоченные, состоящие из нулей массивы)

Рис. 2.5 - График среднего числа сравнений практических и теоретических измерений

Рис. 2.6 - График среднего числа перемещений практических и теоретических измерений

Если графики зависимостей среднего числа сравнений, полученные практически, расположены внутри теоретических плоскостей, то можно сделать вывод, что практические зависимости среднего числа сравнений от числа элементов в массиве были получены верно. Далее произведём проверку средних значений числа сравнений полученных теоретически и практически. Для этого составим программу №2 (см. ПРИЛОЖЕНИЕ F), которая будет осуществлять вычисления по формуле:

 (1.5)

 (1.6)

для разных значений числа элементов сортируемого массива.

Данные для расчётов возьмём из таблиц 2,3,4,5. А результаты вычислений самой программы сведём в таблицу 6. После этого произведём необходимый анализ результатов.

Таблица 6

Результат сравнения теоретических и практических результатов исследований программой №2

Теперь произведём анализ полученных результатов (табл. 6). Проверим, не превышает ли ошибка в исследованиях инженерную точность, т.е. все ли значения ti ≤ 14%.В результате проведённого практического исследования удалось установить, что среднее значение числа сравнений входит в теоретическую плоскость возможных значений числа сравнений для исследуемого алгоритма прямого включения. Так же было установлено, что среднее значение число сравнений, полученное практическим экспериментом, практически совпадает со средним значением числа сравнений, полученным по теоретическим формулам. Их отличие не превышает величины инженерной точности при проведении расчётов.

алгоритм массив сравнение прямой

ЗАКЛЮЧЕНИЕ

В данной курсовой работе был исследован алгоритм сортировки методом прямого включения. Для этого было решено произвести литературный обзор по данному алгоритму и выбрать те формулы, которые позволили бы осуществить теоретическое исследование данного метода. Формулы (1.1) - (1.4) характеризовали число сравнений и перестановок наиболее точно. По этим формулам были найдены средние значения количества перемещений и сравнений для массивов с разным количеством элементов. Для практической части была написана программа, которая генерирует массивы с заданным количеством элементов и порядком элементов, возможен и ручной ввод элементов. При практическом исследовании алгоритма была выявлена зависимость скорости работы алгоритма от предварительной сортировки, сортируемого массива. Т.е. скорость работы алгоритма высока при сортировке небольших массивов, а также при сортировке уже сортированных массивов (полностью или частично). И, напротив, скорость низка при сортировке массивов, отсортированных в обратном порядке. Была написана программа №2 для проверки средних значений числа сравнений и перемещений элементов массива полученных теоретически и практически. В результате проверки было установлено, что отличие числа сравнений и перемещений, полученное практически и значение числа сравнений и перемещений, полученные по теоретическим формулам. не превышает величины инженерной точности при проведении расчётов.

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

Для проведения практического исследования был выбран язык программирования Pascal, на котором написаны программы №1 и №2, которые приведены в ПРИЛОЖЕНИИ E и F.

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

1.       Кнут, Дональд, Эрвин. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. : Пер. с англ. - М. : ООО “И.Д. Вильямс”, 2007. - 832с. : ил.

.        Седжвик Роберт. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск :Пер. с англ./Роберт Седжвик. - К.: Издательство “ДиаСофт”, 2001. - 688с.

.        Структуры и алгоритмы обработки данных. Учебно-методическое пособие по изучению дисциплины/ Сост.:О.Б. Попова; Кубан. гос. технол. ун-т. Каф. Вычислительной техники и АСУ.- Краснодар: Изд. КубГТУ, 2007. - 35с.

.        Ахо А. Структуры данных и алгоритмы/ А. Ахо, Д.Э. Хопкрофт, Д. Ульман. - М.: Издательский дом «Вильямс», 2000.

.        Вирт Н. Алгоритмы и структуры данных. - М.: Издательский дом «Вильямс», 1998.

.        Лойко В.И. Структуры и алгоритмы обработки данных: учебное пособие для вузов. - Краснодар: Изд-во КубГАУ, 2000.

.        Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. - М.: Издательский дом «Вильямс», 2000.

ПРИЛОЖЕНИЕ E

Код программы №1

uses crt;

type mass=array [1..2000]of integer;a:mass;,perem,sravn,sr,m,n,b,i,v,w,z:integer;,sravnsr:real;:byte;insertion;,i, k : Integer;:=0; {peremeshenia}:=0; {sravnenia} i := 2 to n do { Вставляем в уже отсортированную часть элементы с 2 до n }

:= i; {присваиваем переменной к текущий ключ}:= a[i]; {присваиваем переменной х значение ключа}

                    inc(sr); {увеличиваем счётчик сравнений}

                    inc(pr); {увеличиваем счётчик перемещений}

{ Передвигаем на 1 позицию направо элементы,

большие вставляемого элемента (он записан в x) }

{ Условие k > 1 гарантирует, что мы не выйдем за

границу массива, если вставляется элемент,

меньший всех предыдущих.}

(A[k - 1] > x) and (k > 1) do

[k] := a[k - 1];:= k - 1;

                             inc(sr); {увеличиваем счётчик сравнений}

                             inc(pr); {увеличиваем счётчик перемещений};

{ Вставляем элемент в нужную позицию }[k] := x;

                    inc(pr); {увеличиваем счётчик перемещений}

end;;

         procedure print ; { процедура печати массива в строку}i:Integer ;i:=1 to n do(a[i],' ');;

end ;

vozrastanie; { Заполнение массива числами по возрастанию }

var: Integer;

         perem:=0;:=0;

          for z := 1 to m do

          begini := 1 to n do[i] := i;

                   print;

                    writeln;;;

          perem:=perem+pr; {подсчёт перемещений за м кол-во сортировок}

          sravn:=sravn+sr;        {подсчёт сравнений за м кол-во сортировок}   ;

          peremsr:=perem/m; {среднее знач перемещ. за м сортировок}

          sravnsr:=sravn/m; {среднее знач сравнений за м сортировок}

                   ;

ubivanie; { Заполнение массива числами по убыванию }

var: Integer;

          begin

         perem:=0;:=0;

          for z := 1 to m doi := 1 to n do[i] := n - i;

                   print;

                    writeln;;;

                    perem:=perem+pr;

                    sravn:=sravn+sr;                  ;

          peremsr:=perem/m;

          sravnsr:=sravn/m;

;

nul; { Заполнение массива равными числами (0) }

var: Integer;

          begin

         perem:=0;:=0;

          for z := 1 to m doi := 1 to n do[i] := 0;

                   print;

                    writeln;;;

                    perem:=perem+pr;

                    sravn:=sravn+sr;                  ;

          peremsr:=perem/m;

          sravnsr:=sravn/m;

;

sluchainie; { };

         perem:=0;:=0;

          for z := 1 to m doi := 1 to n do[i]:=random(500);

                   print;

                    writeln;;;

                    perem:=perem+pr;

                    sravn:=sravn+sr;                  ;

          peremsr:=perem/m;

          sravnsr:=sravn/m;

                   ;

         procedure ruchnoi; { }

         var: Integer;

          begin

         perem:=0;:=0;

          for z := 1 to m doi := 1 to n do('Vvedite chlen massiva ', i);(a[i]);

         end;

          print;

                    writeln;;;

                    perem:=perem+pr;

                    sravn:=sravn+sr;                 

          peremsr:=perem/m;

          sravnsr:=sravn/m;

;;('Vvedite kolichestvo elementov');(n);

          writeln('Vvedite kolichestvo sortirovok');

          readln(m);

('viberite deistvie: ');

('1. Sgenerirovat massiv sluchainimi chislami');

('2. Sgenerirovat massiv nulaimi');

('3. Sgenerirovat massiv po ubivaniu');

('4. Sgenerirovat massiv po vozrastaniu');

('5. Vvod v ruchnuu');

(punkt);

punkt of

:sluchainie; {выбор метода генерации массива}

:nul;

:ubivanie;

:vozrastanie;

:ruchnoi;;;

('Srednee kol-vo peremeshenii dla ',m,' sortirovok=',peremsr:2:1,#13#10,'srednee kol-vo sravnenii=',sravnsr:2:1);

readln;.

ПРИЛОЖЕНИЕ F

Код программы №2

program Sravn_Teor_i_Pract_issledovanii;;_znacheniya=array[1..100] of record_p,perest_p,sravn_t,perest_t:real;_elem:integer;_znach_sr,otlichie_znach_per:real;;=array[1..1000] of integer;:srednii_znacheniya;,h3:integer;

{Для разного числа исследованений определяет среднее число сравнений, перестановок и записывает их в запись с тремя полями}

procedure vvod_znach_pract_teor(var chislo_tochek:integer);i,chislo_elem_mas:integer;('skolko tochek budet na grafike?');(chislo_tochek);i:=1 to chislo_tochek do('Vvedite chislo elementov massiva dlia poluchenia ',i,'-oi tochki');(chislo_elem_mas);('Vvedite srednee chislo sravnenii , poluchennih prakt. sposobom!');(s[i].sravn_p);('Vvedite srednee chislo sravnenii, poluchennih teoriticheskim sposobom!');(s[i].sravn_t);('Vvedite srednee chislo peremeshenii, poluchennih prakt. sposobom!');(s[i].perest_p);('Vvedite srednee chislo peremeshenii, poluchennih teoriticheskim sposobom!');(s[i].perest_t);[i].chislo_elem:=chislo_elem_mas;;

end;

{Сравнение исследований как практического, так и теоретического}

procedure sravnenie_p_t_analizov(chislo_tochek:integer);i:integer;i:=1 to chislo_tochek do[i].otlichie_znach_sr:=(s[i].sravn_p-s[i].sravn_t)*100/s[i].sravn_p;[i].otlichie_znach_per:=(s[i].perest_p-s[i].perest_t)*100/s[i].perest_p;;;

_znach_pract_teor (h3);_p_t_analizov(h3);;('==================');j:=1 to h3 do('Dla chisla elementov massiva = ',s[j].chislo_elem);('Otlichie prakticheskogo srednego chisla sravnenii ot teoriticheskogo sostovlaet = ',s[j]. otlichie_znach_sr:3:1, '%');('Otlichie prakticheskogo srednego chisla peremeshenii ot teoriticheskogo sostovlaet = ',s[j].otlichie_znach_per:3:1, '%');('==================');;;.