Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Что понимается под сортировкой?

2. Каковы особенности сортировки: вставкой, выбором, обменом, Шел­ла, Хоара, турнирной, пирамидой?

Какова основная идея шейкерной сортировки?

К какой группе методов относится сортировка фон Неймана?

Что включает в себя понятие сложности алгоритма?

В чем состоит методика анализа сложности алгоритмов сортировки?

Методы поиска

Предметы (объекты), составляющие множество, называются его элементами. Элемент множества будет называться ключом и обозначаться латинской буквой «k» с индексом, указывающим номер элемента.

Алгоритмы поиска можно разбить на следующие группы (рис. 2.16).

Задача поиска.

Пусть задано множество ключей {k1,, k2, k3, ..., kn}.

Необходимо отыскать во множестве ключ ki. Поиск может быть завершен в двух случаях:

• ключ во множестве отсутствует;

• ключ найден во множестве.

Рис. 2.16.Методы поиска

2.2.1. Последовательный поиск

В последовательном поиске исходное множество не упорядо­чение, т. е. имеется произвольный набор ключей {k1; k2, k3, ..., kn,}. Метод заключается в том, что отыскиваемый ключ ki после­довательно сравнивается со всеми элементами множества. При этом поиск заканчивается досрочно, если ключ найден.

2.2.2. Бинарный поиск

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

{k1≤k2≤k3≤k4...kn-1≤kn}.

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

Номер центрального элемента находится по формуле

№ эл-та= [n/2] + 1,

где квадратные скобки обозначают, что от деления берется толь­ко целая часть (всегда округляется в меньшую сторону). В методе бинарного поиска анализируются только центральные элементы.

Пример.Дано множество

{7, 8, 12, 16, 18, 20, 30, 38, 49, 50, 54, 60, 61, 69, 75, 79, 80, 81, 95, 101, 123, 198}.

Найти во множестве ключ К= 61.

Шаг 1. № эл-та = [n/2] + 1 = [22/2] + 1 = 12.

K~k12.

61 > 60. Дальнейший поиск в правом подмножестве

(61, 69, 75, 79, 80, 81, 95, 101, 123, 198}.

Значок «~» обозначает сравнение элементов (чисел, значений).

Шаг 2. № эл-та = [n/2] + 1 = [10/2] + 1=6.

К~ k18.

61 < 81. Дальнейший поиск в левом подмножестве

{61, 69, 75, 79, 80}

(относительно предыдущего подмножества).

Шаг 3. № эл-та = [n/2] + 1 = [5/2] + 1 = 3.

K~kl5.

61 < 75. Дальнейший поиск в левом подмножестве

{61, 69}.

Шаг 4. № эл-та = [n/2] + 1 = [2/2] + 1=2.

K~k14.

61 < 69. Дальнейший поиск в левом подмножестве

{61}.

Шаг 5. № эл-та = [n/2]+ 1 = [1/2] + 1 = 1.

K~kl3.

61 = 61.

Вывод: искомый ключ найден под номером 13.

Фибоначчиев поиск

В этом поиске анализируются элементы, находящиеся в по­зициях, равных числам Фибоначчи. Числа Фибоначчи получа­ются по следующему правилу:

каждое последующее число равно сумме двух предыдущих чисел, например:

{1, 2, 3, 5, 8, 13, 21, 34, 55, ...}.

Поиск продолжается до тех пор, пока не будет найден интервал между двумя ключами, где может располагаться отыскивае­мый ключ.

Пример.Дано исходное множество ключей (3, 5, 8, 9, 11, 14, 15, 19, 21, 22, 28, 33, 35, 37, 42, 45, 48, 52}.

Пусть отыскиваемый ключ равен 42 (К= 42).

Последовательное сравнение отыскиваемого ключа будет проводиться в позициях, равных числам Фибоначчи: {1, 2, 3, 5, 8, 13, 21,...}.

Шаг 1. К~ Ki, 42 > 3 => отыскиваемый ключ сравнивается с ключом, стоящим в позиции, равной числу Фибоначчи.

Шаг 2. К~ К2, 42 > 5 => сравнение продолжается с ключом, стоящим в позиции, равной следующему числу Фибоначчи.

Шаг 3. К~ К3, 42 > 8 => сравнение продолжается.

Шаг 4. К~ К5, 42 > 11 => сравнение продолжается.

Шаг 5. К~ K8, 42 > 19 => сравнение продолжается.

Шаг 6. К~ K13, 42 > 35 => сравнение продолжается.

Шаг 7. К~ К18, 42 < 52 => найден интервал, в котором находится отыскиваемый ключ: от 13 до 18 позиции, т. е. {35, 37, 42, 45, 48, 52}.

В найденном интервале поиск вновь ведется в позициях, равных числам Фибоначчи.

2.2.4. Интерполяционный поиск

Исходное множество должно быть упорядочено по возрастанию весов. Первоначальное сравнение осуществляется на расстоянии шага d, который определяется по формуле:

где i — номер первого рассматриваемого элемента; j — номер последнего рассматриваемого элемента; К — отыскиваемый ключ; Кi Kjзначения ключей в i и j позициях;

[ ] — целая часть от числа.

Идея метода заключается в следующем: шаг d меняется по­сле каждого этапа по формуле, приведенной выше (рис. 2.17). Алгоритм заканчивает работу при d= 0, при этом анализируются соседние элементы, после чего делается окончательное решение о результатах поиска.

Рис. 2.17. Алгоритм поиска

Этот метод прекрасно работает, если исходное множество представляет собой арифметическую прогрессию или множест­во, приближенное к ней.

Пример.Дано множество ключей:

{2, 9, 10, 12, 20, 24, 28, 30, 37, 40, 45, 50, 51, 60, 65, 70, 74, 76}.

Пусть искомый ключ равен 70 (К= 70).

Шаг 1. Определим шаг d для исходного множества ключей:

d=[(18-l)(70-2)/(76-2)] = 15.

Сравниваем ключ, стоящий под шестнадцатым порядковым номером в данном множестве, с искомым ключом: К16 ~ К, 70 = 70, ключ найден.

Поиск по бинарному дереву

Использование структуры бинарного дерева позволяет быст­ро вставлять и удалять записи и производить эффективный по­иск по таблице. Такая гибкость достигается добавлением в каждую запись двух полей для хранения ссылок.

Пусть дано бинарное дерево поиска (рис. 2.18).

 

Рис.2.18. Бинарное дерево

Требуется по бинарному дереву отыскать ключ SAG.

При просмотре от корня дерева видно, что по первой букве латинского алфавита название SAG больше чем САР. Следова­тельно, дальнейший поиск будем осуществлять в правой ветви. Это слово больше, чем PIS, — снова идем вправо; оно меньше, чем TAU, — идем влево; оно меньше, чем SCO, и попадаем в узел 8. Таким образом, название SAG должно находиться в узле 8.

При этом узлы дерева имеют следующую структуру (табл. 2.1).

Таблица 2.1. Структура узлов дерева

Пример.Исходное множество ключей должно быть упорядо­чено по возрастанию. Переходим от линейного списка к по-1 строению бинарного дерева поиска (рис. 2.19), где корнем дере­ва является центральный элемент множества

где N — количество элементов множества.

Рис. 2.19.Бинарное дерево поиска

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

{2, 4, 5, 6, 7, 9, 12, 14, 18, 21, 24, 25, 27, 30, 32, 33, 34, 37, 39};

Искомый ключ К= 24;

Всего элементов N= 19; Nцентр = [19/2] +1 = 10.

Поиск ключа К = 24 по бинарному дереву от корня до листь­ев показан на рис. 2.19.

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...