17 Линейный поиск. Поиск делением пополам (двоичный поиск).

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

Условие окончания:

• Элемент найден, т.е. а[i]=х.

• Весь массив просмотрен, а элемента не обнаружено.

While (i<n) and (a[i]<>x) do i:=i+1;

Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i:

(0≤i<n) and (для всех k: 0≤k<i; a[k]≠x).

Условие окончания: ((i=n) or (a[i]=x)) and (для всех k: 0≤k<i; a[k]≠x).

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

Равенство i=n свидетельствует о том, что совпадения не было. Очевидно, что окончания цикла гарантировано и за конечное число шагов мы можем достичь предела n.

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

Основная идея: выбрать случайные элементы a[m] и сравнить с аргументом поиска х, если он равен х, то конец поиска, если меньше х, то все элементы с индексами меньше или равно m можно исключить из рассмотрения, если же он больше х, то исключаются элементы с индексом больше или равно m.

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

18 Простые алгоритмы сортировки.

Под сортировкой понимается процесс перестановки объектов данного множества в определенном порядке. Цель сортировки – облегчить последующий поиск элементов в отсортированном множестве.

Обычно функция упорядочивания не вычисляется по какому-либо правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называется ключом элемента.

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

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

Сортировка простыми включениями. Элементы условно разделяются на готовую последовательность а₀..а_i-1 и входную последовательность а_i..а_n. На каждом шаге, начиная с i=2 и затем увеличивая i на единицу берут i-тый элемент входной последовательности и передают в готовую последовательность вставляя его на подходящее место.

for i:=2 to n do

begin

x:=a[i];

“вставить х на нужное место”

end;

При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы «просеивать» сравнивая его с очередным элементом а_g и либо вставлять х, либо пересылать а_g вправо и продвигаться налево.

«Просеивание» может закончиться при двух различных условиях:

Найдем элемент а_g с ключом меньшим чем х.

Достигнут левый конец готовой последовательности.

Сортировка с простым выбором. Основана на следующем правиле:

Выбираем элемент с наименьшим ключом.

Он меняется местами с первым элементом массива.

Эти операции повторяются с оставшимися (n-1) элементом, потом с (n-2) элементом, пока не останется один наибольший элемент.

Цикл выглядит следующим образом:

for i:=1 to n-1 do

begin

“присвоим k индекс наименьшего элемента из массива (a[i]..a[n]) и поменять местами a_i и a_k”;

end;

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

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

Сортировка простым обменом (Пузырек). Основана на принципе сравнения и обмена пары соседних элементов до тех пор пока не будут рассортированы все элементы.

Procedure Puzirek;

var i,j,x: integer;

begin

for i:=2 to n do

for j:=n downto i do

if a[j-1]>a[j]

then

begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;

end;

end;