Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Краткое описание алгоритмов поиска




Алгоритм сортировки Хоара (QuickSort).

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

Реализация алгоритма, как правило, предполагает использование рекурсии. Суть алгоритма заключается в следующем: на каждом шаге находится средний элемент рассматриваемой части массива и при необходимости осуществляются обмены элементов относительно среднего элемента таким образом, чтобы все элементы слева были меньше либо равны по отношения к среднему, а справа – больше либо равны.

В дальнейшем рекурсивно вызывается та же подпрограмма для левой и правой частей массива, которые интерпретируется как отдельный массив, упорядочиваемый по вышерассмотренному алгоритму.

Рекурсивные вызовы прекращаются, когда длина сортируемого массива вырождается в 1 или 2 элемента.

 

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

Рассмотрим 2 часто используемых алгоритма поиска: поиск с помощью последовательного перебора элементов массива (последовательный поиск) и бинарный поиск.

 

Последовательный поиск может быть применен для структур данных как с произвольным доступом, так и с последовательным доступом в не зависимости от упорядоченности элементов. Причем эффективность последовательного поиска определяется расположением (наличием) искомого элемента и структурой данных.

Суть последовательного поиска заключается в следующем: происходит последовательный перебор элементов от 0-ого до N - 1-ого, и на каждом шаге цикла сравниваем текущий элемент с искомым. Если они равны, то констатируем то, что элемент найден и прекращаем поиск. Если массив просмотрен до конца и элемент не найден, то его нет в массиве.

Если необходимо найти все указанные элементы в массиве, то при обнаружении 1-ого подходящего элемента поиск продолжается, пока не просмотрим все элементы массива.

 

Бинарный поиск. Бинарный поиск применим только для отсортированных массивов. Суть бинарного поиска заключается в следующем: на каждом шаге массив делится пополам. Искомый элемент сравнивается со средним элементом массива. Если они равны, то поиск закончен удачно. Если же искомый элемент меньше среднего, то берется левая часть массива (исключая средний элемент), иначе – правая. Далее над левой (правой) частью выполняются вышеописанные действия до тех пор, пока не найден искомый элемент или очередная левая (правая) части массива не вырождаются в 1 элемент, не равный искомому.

Если при использовании бинарного поиска нужно найти все элементы массива, равные искомому, то следует учитывать, что т.к., массив отсортирован, то все равные элементы расположены непрерывными группами. Следовательно, если найден один элемент группы, то слева или справа от него будут и остальные равные ему элементы.

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

Задание

 

Используя шаблон программы реализовать следующие алгоритмы сортировки и поиска на языке C++:

 

1. Для получения 100% от числа баллов, отводимых на лабораторную работу, необходимо написать программу, которая реализует:

А) Сортировку методами (причем необходимо осуществить оценку количества просмотров массива, а также количества перестановок элементов для каждого из реализованных алгоритмов):

· пузырька (с оптимизацией для определения упорядоченности массива);

· минимумов;

· вставки;

· минимумов и максимумов одновременно;

· Шелла (2 варианта: с использованием деления массива на части, длины которых кратны степеням двойки и применением последовательности Седжвика);

· quick sort (Хоара).

B) Поиск:

· последовательный;

· бинарный (с использованием и без использования рекурсии).

Необходимо представить отчет, который будет содержать:

· количество элементов массива (не менее 100000);

· время работы каждого из алгоритмов сортировки для массива указанной длины;

· количество просмотров массива и перестановок для каждого алгоритма сортировки массива указанной длины;

· выводы (оценка эффективности реализованных алгоритмов сортировки);

· оценку эффективности использования рекурсии для реализации алгоритма бинарного поиска.

 

2. Для получения 80% от числа баллов, отводимых на лабораторную работу, необходимо написать программу, которая реализует:

А) Сортировку методами:

· пузырька (с оптимизацией для определения упорядоченности массива);

· минимумов;

· вставки;

· минимумов и максимумов одновременно;

· Шелла;

· quick sort (Хоара).

B) Поиск:

· последовательный;

· бинарный (с использованием или без использования рекурсии).

Необходимо представить отчет, который будет содержать:

· количество элементов массива (не менее 100000);

· время работы каждого из алгоритмов сортировки для массива указанной длины;

· выводы (оценка эффективности реализованных алгоритмов сортировки);

· обоснование выбора рекурсивной или не рекурсивной реализации бинарного поиска.

 

3. Для получения 65% от числа баллов, отводимых на лабораторную работу, необходимо написать программу, которая реализует:

А) Сортировку методами:

· пузырька (с оптимизацией для определения упорядоченности массива);

· минимумов;

· вставки;

· минимумов и максимумов одновременно;

B) Поиск:

· последовательный;

· бинарный (с использованием или без использования рекурсии).

Необходимо представить отчет, который будет содержать:

· количество элементов массива (не менее 100000);

· время работы каждого из алгоритмов сортировки для массива указанной длины;

· выводы (оценка эффективности реализованных алгоритмов сортировки);

 

Сортировка производится по возрастанию.

 

Прототипы всех функций по сортировке и поиску должны быть описаны в файлах sort.h и search.h, а исполнимый код этих функций должен находиться в.obj файлах (получаются путем компиляции.cpp файлов, причем в данном случае.cpp файлы не должны содержать функцию main) sort.obj и search.obj, которые подключаются к итоговому проекту на этапе линковки. Для этого необходимо выбрать пункт меню Project\Settings или нажать сочетание клавиш Alt+F7 и в открывшемся диалоговом окне выбрать вкладку Link. На этой вкладке необходимо в окне Object/library modules дописать эти два.obj файла.

Для избежания многократного подключения одного и того же файла заголовков рекомендуется применять следующий прием:

 

#ifndef имя_файла_заголовков_INCLUDE

#define имя_файла_заголовков_INCLUDE

// содержимое файла заголовков

#endif

 

 




Поделиться с друзьями:


Дата добавления: 2017-01-14; Просмотров: 446; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.