Алгоритмы поиска и упорядочения массива.

Алгоритмы поиска

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

ЛИНЕЙНЫЙ ПОИСК

Простейший алгоритм поиска - линейный. Эталонный массив просматривается последователь-но от первого до последнего элемента.

Наихудший случай - слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.

Достоинство – простота реализации. Недостаток – большое время.

Если используется for всегда выполняется ровно n операций сравнения, независимо от того, найдено слово или нет. Разумно прекращать поиск если, слово найдено (если не требуется найти все вхождения слова).

При равномерном распределении элементов в массиве среднее время поиска обычно пропор-ционально величине n/2.

Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X.

Различают первое вхождение элемента в список, последнее вхождение, все вхождения.

ПОИСК С БАРЬЕРОМ

Идея поиска с барьером: не проверять каждый раз в цикле условие достижения границы мас-сива.

Это обеспечивают, установив в массиве: любой элемент, который удовлетворяет условию по-иска. Тем самым будет ограничено изменение индекса. В качестве баръера можно установить искомый элемент добавив его в конец массива.

Достоинство: на одну проверку меньше в цикле.

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

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

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

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

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

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

Идея алгоритма: массив каждый раз делится пополам и выбирается та часть, где может нахо-диться нужный элемент. Деление продолжается пока подмассив больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска.

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

В алгоритме двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каж-дый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алго-ритма порядка логарифма N по основанию 2, где N - количество элементов массива.

ИНТЕРПОЛЯЦИОННЫЙ ПОИСК

Предполагается, что массив упорядочен по величинам ключей элементов.

Идея алгоритма: предполагается равномерное распределение величин в некотором их диапазо-не от u до l. Поэтому, зная величину Х ключа поиска, можно предсказать более точное положе-ние искомой записи, чем просто в середине некоторого отрезка файла. Интерполяционный по-иск ассимптотически предпочтительнее бинарного.

Алгоритм основан на формуле i=l+trunc((u-l)*(X-K[l])/(K[u]-K[l]))

Время t работы алгоритма оценивается формулой: t=a*logN

ПОИСК минимума и максимума

При поиске минимума или максимума используют дополнительную переменная min (или max):

1) промежуточной переменной присваивается значение первого числа из последовательности, т.е. принимается, что первое число является текущим минимумом (максимумом);

2) начиная со второго числа, производится сравнение этого числа со значением переменной min (или max) и если число из массива меньше min (больше max), то на место min (max) записыва-ется это число. Теперь это число будет текущим минимумом (максимумом);

После просмотра всех чисел в переменной min (или max) будет находиться окончательное зна-чение

минимума (или максимума).

Алгоритмы сортировки массивов

Задача сортировки массива, то есть перестановки элементов массива так, чтобы они были упорядочены по возрастанию, убыванию или другой аналогичной характеристике, является одной из основных технических задач программирования. С этой задачей мы сталкиваемся и при записи фамилий учеников в классном журнале, и при подведении итогов соревнований, и даже при упорядочении игральных карт, например, при игре в преферанс. Очень часто сортировка используется как первый шаг в алгоритме решения более сложной задачи. Рассмотрим наиболее простые алгоритмы сортировки массивов и подсчитаем их вычислительную сложность (см. “Теория алгоритмов”).

“Пузырьковая” сортировка

Традиционно наиболее простой в реализации считается так называемая “пузырьковая” сортировка. Суть ее в случае упорядочения по неубыванию заключается в следующем. Будем просматривать слева направо все пары соседних элементов: a1 и a2, a2 и a3, …, an-1 и an. Если при этом ai > ai+1, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своем) месте. Об остальных элементах ничего определенного сказать невозможно. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. И так далее. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров при этом равно N–1. Приведем фрагмент программы, реализующий описанный алгоритм:

for j:= 1 to n — 1 do

{цикл по просмотрам}

for i:= 1 to n — j do

{просмотр массива}

if a[i] > a[i + 1] then

begin

x:= a[i];

a[i]:= a[i + 1];

a[i + 1]:= x

end;

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

Количество сравнений в данном алгоритме равно

N – 1 + N – 2 + N – 3 +... + 1 = N(N – 1)/2.

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

3(N – 1 + N – 2 + N – 3 +... + 1) = 3N(N – 1)/2.

Говорят, что данный алгоритм имеет квадратичную сложность как по числу сравнений, так и по числу присваиваний. “Пузырьковым” он называется потому, что в результате каждого просмотра максимальный из оставшихся элементов оказывается на своем месте — “всплывает”. По-другому такая сортировка называется обменной.

Сортировка “прямым выбором”

Рассмотрим алгоритм сортировки, основанный на принципиально иной идее. Найдем минимальный элемент в массиве и поменяем его с первым элементом массива. В результате он окажется на своем месте. Затем найдем минимальный элемент среди оставшихся и поменяем его со вторым элементом. На N–1-м шаге мы закончим упорядочивание нашего массива. Такой алгоритм называется сортировкой прямым выбором. Приведем фрагмент программы, реализующий описанный алгоритм:

for i:= 1 to n — 1 do

begin

mini:= i;

for j:= i + 1 to n do

{ищем минимальный элемент}

if a[j] < a[mini] then mini:= j

{меняем минимальный элемент с i-м}

x:= a[i];

a[i]:= a[mini];

a[mini]:= x

end;

Количество выполняемых операций в данном алгоритме всегда одинаково. Для сравнений оно равно

N – 1 + N – 2 + N – 3 +... + 1 = N(N – 1)/2,

а для присваиваний — всего 3(N – 1).

Сортировка “подсчетом”

То есть данный алгоритм квадратичный по числу сравнений и линейный (эффективный) по числу присваиваний.

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

const maxn = 10000;

var d: array[0..9] of integer;

{массив для подсчета}

a: array[1..maxn] of 0..9;{массив цифр}

n, i, j, k: integer;

begin

readln(n); {n — количество цифр}

for i:= 1 to n do a[i]:= random(10);

for j:= 0 to 9 do d[j]:= 0;

for i:= 1 to n do {подсчет каждой цифры}

d[a[i]]:= d[a[i]] + 1;

k:= 0;

for j:= 0 to 9 do {заполняем a заново}

for i:= 1 to d[j] do

begin

k:= k + 1;

a[k]:= j

end

end.

Заметим, что эта программа работает верно и в случае, когда какой-либо из цифр во вводимой последовательности нет совсем. Подобный алгоритм называют сортировкой подсчетом. Его вычислительная сложность в общем случае составляет 2N + 2m операций, где m — количество различных значений среди элементов в массиве (в нашем примере их было всего 10). Очевидно, что если m Ј N и мы можем отвести память для подсчета количества каждого из m возможных значений для элементов массива, то алгоритм будет иметь линейную сложность относительно N.

Дата добавления: 2017-02-01