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

 

Таблица 4

 

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

(неупорядоченные массивы)

 

N	10	20	30	40	50	60	70	80	90	100
sravnсрпр1	31,9	127,2	247,3	408,7	675,2	950,1	1328,7	1612,7	2019,1	2554,1
sravnсрпр2	35,8	111,2	251,1	434	667,2	909,4	1215,6	1645,1	2094,5	2560,1
peremсрпр1	40,9	108,2	276,3	447,7	724,2	1009,1	1397,7	1691,7	2108,1	2653,1
peremсрпр2	44,8	130,2	280,1	473	716,2	968,4	1284,6	1724,1	2183,5	2659,1

                                   

                                                    

  Таблица 5      

  

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

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

 

N	10	20	30	40	50	60	70	80	90	100
sravnупоряд	9	19	29	39	49	59	69	79	89	99
sravnобрупоряд	54	209	464	819	1274	1829	2484	3239	4094	5049
sravnнули	9	19	29	39	49	59	69	79	89	99
peremупоряд	18	38	58	78	98	118	138	158	178	198
peremобрупоряд	63	228	493	858	1323	1888	2553	3318	4183	5148
peremнули	18	38	58	78	98	118	138	158	178	198

                                 

        

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

                                        теоретических измерений.

 

 

 

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

                                        теоретических измерений.

                         

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

              _(1.5)

              (1.6)

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

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

 

Таблица 6

 

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

 

N	10	20	30	40	50	60	70	80	90	100
tsravn, %	3	5	13	13	10	10	9	3	6	13
ƒperemesh,%	11	11	6	13	13	3	12	13	10	9

 

 

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

                                              ЗАКЛЮЧЕНИЕ

 

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

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

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

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

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

 

1. Кнут, Дональд, Эрвин. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. : Пер. с англ. – М. : ООО “И.Д. Вильямс”, 2007. – 832с. : ил.
2. Седжвик Роберт. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск :Пер. с англ./Роберт Седжвик. – К.: Издательство “ДиаСофт”, 2001. – 688с.
3. Структуры и алгоритмы обработки данных. Учебно-методическое пособие по изучению дисциплины/ Сост.:О.Б. Попова; Кубан. гос. технол. ун-т. Каф. Вычислительной техники и АСУ.- Краснодар: Изд. КубГТУ, 2007. – 35с.
4. Ахо А. Структуры данных и алгоритмы/ А. Ахо, Д.Э. Хопкрофт, Д. Ульман. – М.: Издательский дом «Вильямс», 2000.
5. Вирт Н. Алгоритмы и структуры данных. – М.: Издательский дом «Вильямс», 1998.
6. Лойко В.И. Структуры и алгоритмы обработки данных: учебное пособие для вузов. – Краснодар: Изд-во КубГАУ, 2000.
7. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Издательский дом «Вильямс», 2000.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ E

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

 

 

 

uses crt;

type mass=array [1..2000]of integer;

var a:mass;

pr,perem,sravn,sr,m,n,b,i,v,w,z:integer;

peremsr,sravnsr:real;

punkt:byte;

procedure insertion;

    var

      x,i, k : Integer;

    begin

     pr:=0; {peremeshenia}

      sr:=0; {sravnenia}

      for i := 2 to n do      { Вставляем в уже отсортированную часть элементы с  2 до n }

 

        begin

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

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

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

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

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

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

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

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

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

 

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

 

            begin

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

              k := k - 1;

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

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

            end;

                                                   { Вставляем элемент в нужную позицию }

                  a[k] := x;      

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

        end;

    end;

 

procedure print ;         { процедура печати массива в строку}

var i:Integer ;

begin

  for i:=1 to n do

    write(a[i],' ');

  Writeln ;

end ;

 

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

 

    var

      i : Integer;

    begin

perem:=0;

    sravn:=0;

for z := 1 to m do

begin

      for i := 1 to n do

        a[i] := i;

  print;

  writeln;

         insertion;

          print;

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

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

      end;

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

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

 

    end;

 

 

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

    var

      i : Integer;

   begin

perem:=0;

    sravn:=0;

for z := 1 to m do

    begin

      for i := 1 to n do

        a[i] := n - i;

print;

  writeln;

          insertion;

          print;

  perem:=perem+pr;

  sravn:=sravn+sr;  

      end;

  peremsr:=perem/m;

  sravnsr:=sravn/m;

 

 

    end;

 

 

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

    var

      i : Integer;

  begin

perem:=0;

    sravn:=0;

for z := 1 to m do

    begin

      for i := 1 to n do

        a[i] := 0;

print;

  writeln;

          insertion;

          print;

  perem:=perem+pr;

  sravn:=sravn+sr;  

      end;

  peremsr:=perem/m;

  sravnsr:=sravn/m;

 

 

    end;

 

procedure sluchainie; {  }

  begin

    randomize;

perem:=0;

    sravn:=0;

for z := 1 to m do

    begin

      for i := 1 to n do

        a[i]:=random(500);

print;

  writeln;

          insertion;

          print;

  perem:=perem+pr;

  sravn:=sravn+sr;  

      end;

  peremsr:=perem/m;

  sravnsr:=sravn/m;

 

    end;

 

procedure ruchnoi; {  }

var

      i : Integer;

begin

perem:=0;

    sravn:=0;

for z := 1 to m do

    begin

      for i := 1 to n do

          begin

        writeln('Vvedite chlen massiva ', i);

         readln(a[i]);

end

      end;

  print;

  writeln;

          insertion;

          print;

  perem:=perem+pr;

  sravn:=sravn+sr;  

  peremsr:=perem/m;

  sravnsr:=sravn/m;

 

    end;

begin

clrscr;

   writeln('Vvedite kolichestvo elementov');

    readln(n);

writeln('Vvedite kolichestvo sortirovok');

  readln(m);

 

     writeln('viberite deistvie: ');

 

     writeln('1. Sgenerirovat massiv sluchainimi chislami');

 

     writeln('2. Sgenerirovat massiv nulaimi');

 

     writeln('3. Sgenerirovat massiv po ubivaniu');

 

     writeln('4. Sgenerirovat massiv po vozrastaniu');

 

     WriteLn('5. Vvod v ruchnuu');

 

ReadLn(punkt);

 

  case punkt of

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

    2:nul;

     3:ubivanie;

      4:vozrastanie;

       5:ruchnoi;

  end;

writeln;

 

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

 

       readln;

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ F

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

 

program Sravn_Teor_i_Pract_issledovanii;

uses

crt;

type

srednii_znacheniya=array[1..100] of record

sravn_p,perest_p,sravn_t,perest_t:real;

chislo_elem:integer;

otlichie_znach_sr,otlichie_znach_per:real;

end;

massiv=array[1..1000] of integer;

var

s:srednii_znacheniya;

j,h3:integer;

 

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

procedure vvod_znach_pract_teor(var chislo_tochek:integer);

var i,chislo_elem_mas:integer;

begin

writeln('skolko tochek budet na grafike?');

readln(chislo_tochek);

for i:=1 to chislo_tochek do

begin

writeln('Vvedite chislo elementov massiva dlia poluchenia ',i,'-oi tochki');

readln(chislo_elem_mas);

writeln('Vvedite srednee chislo sravnenii , poluchennih prakt. sposobom!');

readln(s[i].sravn_p);

writeln('Vvedite srednee chislo sravnenii, poluchennih teoriticheskim sposobom!');

readln(s[i].sravn_t);

writeln('Vvedite srednee chislo  peremeshenii, poluchennih prakt. sposobom!');

readln(s[i].perest_p);

writeln('Vvedite srednee chislo  peremeshenii, poluchennih teoriticheskim sposobom!');