Исследование алгоритма сортировки методом прямого включения - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Исследование алгоритма сортировки методом прямого включения
Принцип работы алгоритма бинарного поиска в массиве. Способы исследования алгоритма "прямое включение". Формулы зависимости числа сравнений от элементов в массиве. Графики среднего числа сравнений и перемещений практических и теоретических измерений.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
СОРТИРОВКА, ПРЯМОЕ ВКЛЮЧЕНИЕ, ЧИСЛО СРАВНЕНИЙ, СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ГРАФИК ЗАВИСИМОСТИ, МАКСИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ, МИНИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ,
В данной курсовой работе был рассмотрен метод сортировки прямым включением(вставкой). Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i- элемент входной последовательности и вставляем его на нужное место в готовую.
Были проведены два эксперимента с пятью массивами разной длинны, в которых проводился поиск десяти разных ключей по десять раз в каждом массиве. Эксперименты позволили увидеть работу метода и рассчитать среднее, максимальное и минимальное количество сравнений при проведении поиска.
Основными моментами проведённого исследования были составление таблиц и графиков зависимости сравнений, что дало возможность сделать вывод о том, что результаты большого количества экспериментов проведенных практическим путем позволяют подтверждать результаты проведенные теоретическим путем.
1. ЛИТЕРАТУРНЫЙ ОБЗОР ПО АЛГОРИТМУ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ
1.1 Краткие теоретические сведения об алгоритме прямое включение
1.2 Выбор материала для проведения теоретического исследования
2. ИССЛЕДОВАНИЕ АЛГОРИТМА СОРТИРОВКИ МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ
2.1 Теоретическое исследование алгоритма прямое включение
2.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,] были предложены следующие зависимости числа сравнений от числа элементов в массиве :
формула зависимости максимального числа сравнений от числа элементов в массиве;
формула зависимости минимального числа сравнений от числа элементов в массиве;
формула зависимости максимального числа перемещений от числа элементов в массиве;
формула зависимости минимального числа перемещений от числа элементов в массиве.
Построим по формулам (2.1) - (2.2) графики зависимостей максимального и минимального числа сравнений для бинарного поиска.
Чтобы построить графики зависимостей максимального и минимального числа сравнений для метода прямого включения, мы возьмем десять произвольных массивов с числом элементов от 10 до 100 и подставим их значения в формулы (1.2) и (1.3), результаты запишем в таблицу(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)=( sravn max (n) + sravn min (n))/2 (1.5)
perem ср теор=( peremmax (n)+ peremmin (n))/2. (1.6)
Средние значения числа сравнений из табл. 1
Средние значения числа перемещений из табл. 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 Практическое исследование алгоритма прямого включения
Для того, чтобы провести практическое исследование данного алгоритма составим программу, которая будет определять точки sravn cpпр и perem српр в зависимости от значения числа элементов используемого массива и его упорядоченности(см. ПРИЛОЖЕНИЕ E). Эксперимент проведем десять раз, в каждом массиве поиск будет проводиться по десять раз, для нахождения sravn cpпр(n) и perem српр (n).Полученные результаты сведём в таблицу 4 и 5. Далее по данным таблиц 4 и 5 построим точки на графике (рис. 2.5 ), соединив которые получим графики зависимостей среднего числа сравнений и перемещений от числа сортируемых элементов массива, sravn cpпр(n) и perem српр (n), полученные практическим способом.
Результаты, полученные при двух практических исследованиях (неупорядоченные массивы)
Результаты, полученные при трёх практических исследованиях (упорядоченные, обратно упорядоченные, состоящие из нулей массивы)
Рис. 2.5 - График среднего числа сравнений практических и теоретических измерений
Рис. 2.6 - График среднего числа перемещений практических и теоретических измерений
Если графики зависимостей среднего числа сравнений, полученные практически, расположены внутри теоретических плоскостей, то можно сделать вывод, что практические зависимости среднего числа сравнений от числа элементов в массиве были получены верно. Далее произведём проверку средних значений числа сравнений полученных теоретически и практически. Для этого составим программу №2 (см. ПРИЛОЖЕНИЕ F), которая будет осуществлять вычисления по формуле:
для разных значений числа элементов сортируемого массива.
Данные для расчётов возьмём из таблиц 2,3,4,5. А результаты вычислений самой программы сведём в таблицу 6. После этого произведём необходимый анализ результатов.
Результат сравнения теоретических и практических результатов исследований программой №2
Теперь произведём анализ полученных результатов (табл. 6). Проверим, не превышает ли ошибка в исследованиях инженерную точность, т.е. все ли значения ti ? 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.
type mass=array [1..2000]of integer;
pr,perem,sravn,sr,m,n,b,i,v,w,z:integer;
for i := 2 to n do { Вставляем в уже отсортированную часть элеме н ты с 2 д о n }
k := i; { присваиваем переменной к текущий ключ }
x := a[i]; { присваиваем переменной х значение ключа }
inc(sr); { увеличиваем счётчик сравнений }
inc(pr); { увеличиваем счётчик перемещений }
{ Передвигаем на 1 позицию направо элементы,
большие вставляемого элемента (он записан в x) }
{ Условие k > 1 гарантирует, что мы не выйдем за
границу массива, если вставляется элемент,
while (A[k - 1] > x) and (k > 1) do
inc(sr); { увеличиваем счётчик сравнений }
inc(pr); { увеличиваем счётчик перемещений }
{ Вставляем элемент в нужную позицию }
inc(pr); { увеличиваем счётчик перемещений }
procedure print ; { процедура печати массива в строку }
procedure vozrastanie; { Заполнение массива числами по возрастанию }
perem:=perem+pr; { подсчёт перемещений за м кол - во сортир о вок }
sravn:=sravn+sr; { подсчёт сравнений за м кол-во сортир о вок }
peremsr:=perem/m; { среднее знач перемещ. за м сортировок }
sravnsr:=sravn/m; { среднее знач сравнений за м сортировок }
procedure ubivanie; { Заполнение массива числами по убыванию }
procedure nul; { Заполнение массива равными числами (0) }
writeln('Vvedite chlen massiva ', i);
writeln('Vvedite kolichestvo elementov');
writeln('Vvedite kolichestvo sortirovok');
writeln('1. Sgenerirovat massiv sluchainimi chislami');
writeln('2. Sgenerirovat massiv nulaimi');
writeln('3. Sgenerirovat massiv po ubivaniu');
writeln('4. Sgenerirovat massiv po vozrastaniu');
1:sluchainie; { выбор метода генерации массива }
writeln('Srednee kol-vo peremeshenii dla ',m,' sortir o vok=',peremsr:2:1,#13#10,'srednee kol-vo sravnenii=',sravnsr:2:1);
program Sravn_Teor_i_Pract_issledovanii;
srednii_znacheniya=array[1..100] of record
sravn_p,perest_p,sravn_t,perest_t:real;
otlichie_znach_sr,otlichie_znach_per:real;
{ Для разного числа исследованений определяет среднее число сравнений, п е рестановок и записывает их в запись с тремя полями }
procedure vvod_znach_pract_teor(var chislo_tochek:integer);
writeln('skolko tochek budet na grafike?');
writeln('Vvedite chislo elementov massiva dlia poluchenia ',i,'-oi tochki');
writeln('Vvedite srednee chislo sravnenii , poluchennih prakt. sposobom!');
writeln('Vvedite srednee chislo sravnenii, poluchennih teoriticheskim sposobom!');
writeln('Vvedite srednee chislo peremeshenii, poluchennih prakt. sposobom!');
writeln('Vvedite srednee chislo peremeshenii, poluchennih teoriticheskim spos o bom!');
{ Сравнение исследований как практического, так и теоретического }
procedure sravnenie_p_t_analizov(chislo_tochek:integer);
s[i].otlichie_znach_sr:=(s[i].sravn_p-s[i].sravn_t)*100/s[i].sravn_p;
s[i].otlichie_znach_per:=(s[i].perest_p-s[i].perest_t)*100/s[i].perest_p;
writeln('Dla chisla elementov massiva = ',s[j].chislo_elem);
writeln('Otlichie prakticheskogo srednego chisla sravnenii ot teoriticheskogo so s tovlaet = ',s[j]. otlichie_znach_sr:3:1, '%');
writeln('Otlichie prakticheskogo srednego chisla peremeshenii ot teoritic h eskogo sostovlaet = ',s[j].otlichie_znach_per:3:1, '%');
Алгоритмическое решение задач как метод формализации. Реализация простейшей самоорганизующейся таблицы с самоорганизацией методом транспозиции. Описание модулей алгоритма и листинг программы для определения функциональной зависимости в массиве данных. курсовая работа [219,9 K], добавлен 25.11.2009
Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных. контрольная работа [573,6 K], добавлен 09.11.2010
Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне. контрольная работа [32,8 K], добавлен 20.01.2012
Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения. курсовая работа [23,1 K], добавлен 24.05.2015
Разработка программы, сортирующей массивы данных различного типа методом подсчета. Основные шаги алгоритма сортировки, ее свойства и модификация подсчетом. Целесообразность применения сортировки подсчетом. Условия эффективности алгоритма сортировки. лабораторная работа [438,5 K], добавлен 16.07.2015
Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов. курсовая работа [43,8 K], добавлен 19.10.2010
Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов. лабораторная работа [20,2 K], добавлен 03.12.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Исследование алгоритма сортировки методом прямого включения курсовая работа. Программирование, компьютеры и кибернетика.
Отчет по практике по теме Характеристика организации 'Морозпродукт'
Контрольная Работа C
Архив Магистерских Диссертаций
Учебное пособие: Методические указания по изучению предмета «Конструкционные и электротехнические материалы»
Реферат: Главнейшие периоды в истории русской педагогии и их характер
Контрольная работа: Философия Эпикура 3
Топик: Кроссворд
Дипломная работа: Психологический портрет младших школьников с различным статусом в социометрической иерархии
Курсовая работа по теме Проект разведочной скважины глубиной 540 метров
Реферат: Состав нефти и классификация
Проблемный анализ романа "Пролетая над гнездом кукушки"
Биосфера Реферат Экология
9 Мая День Победы Реферат
Курсовая работа: Обеспечение занятости населения региона и создание новых рабочих мест
Реферат По Права Рф
Контрольная работа по теме Основные понятия менеджмента
Реферат Устройства Ввода Вывода
Курсовая работа по теме Характеристика различных подходов к определению категории "источник права"
Курсовая работа: Планирование на предприятии 8
Реферат: Чудовий світ алмазів
Создание имиджа фирмы средствами паблик рилейшнз - Маркетинг, реклама и торговля реферат
Деятельность классного руководителя в условиях современной школы - Педагогика курсовая работа
Строение и жизненный цикл чешуекрылых - Биология и естествознание реферат