Курсовая работа на тему: Литературный обзор по алгоритму сортировки прямым включением

Введение

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

Оглавление

- Введение

- Литературный обзор по алгоритму сортировки прямым включением

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

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

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

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

- Практическое исследование алгоритма прямое включение ЗАКЛЮЧЕНИЕ

- Список используемой литературы

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

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

Заключение

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

Список литературы

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ Е

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

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

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

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

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

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

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

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

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

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

(А[к - 1] > x) and (к > 1) dо

[к] := а[к - 1];:= к - 1;

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

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

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

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

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

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

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

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

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

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

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

perem:=perem+рr;

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

perem:=perem+рr;

perem:=perem+рr;

perem:=perem+рr;

('3. Sgenerirovat massiv ро ubivaniu');

('4. Sgenerirovat massiv ро vozrastaniu');

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