Return -1; // элемент не найден

end;

Двоичный поиск – метод дихотомии (делим упорядоченный массив по середине: попали – ура, не попали – смотрим, в которой половине находится искомый элемент и ищем там)

При выборе среднего значения т максимальное число сравнений равно [log2 N] + 1. То есть, поиск в упорядоченном множестве с прямым доступом к элементам также эффективен, как и в дереве поиска, и намного быстрее линейного поиска с числом сравнений N/2. Однако вставка и удаление элемента в упорядоченную таблицу дороже, чем в дереве поиска.

while((low <= high)&&(!found)) {

mid=(low+high)/2;

if(keys[mid] == key) found = 1;

else if(key > keys[mid]) low = mid + 1;

else high = mid - 1;

}

if (found==1) return mid;

if(found==0) {

printf("Record not found!\n");

return -1;

}

 

 

 

33 Поиск по образцу в последовательностях и таблицах.

Поиск в последовательности – поиск в последовательности s из Н элементов последовательности р из М, меньше или равно Н, элементов (выдаёт первое вхождение, а точнее индекс начала первого вхожления).

Прямолинейный метод поиска: 1) ищем вхождение первого элемента

2) поэлементно сравниваем, если не совпадает → переходим к элементу из п.1, берём следующий за ним и возвращаемся в п.1

В таблицах поиск отличается от поиска в массиве тем, что элемент сам по себе составной (“ключ”, по которому мы ищем, и значение, соответствующее данному ключу)

{сам ключ может быть словом или строкой проверка на совпадение строк – политерное сравнение до первого расхождения}

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

б) размер НЕ задаётся (указывается), а сама строка простирается от начала до терминатора (ограничивающего элемента) (предпочтительнее)

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

 

Алгоритм Кнута-Морриса-Пратта

В 1977 году Д.Кнут, В.Морис и В.Пратт опубликовали алгоритм, требующий только Н сравнений даже в самом плохом случае, вместо Н*М (Морис разработал алгоритм отдельно от Кнута и Пратта, но печатались они вместе)

Идея: начиная каждый раз сравнение объекта со строкой мы не забываем ценную информацию (как в прямолинейный метод поиска из п. 32) о тех элементах, которые уже просмотрели и сравнили.

Технически это просмотр объекта на самоподобие (фрактальность) и составление таблицы D, в которой для каждого случая не полного прохода по объекту (нашли первое не полное вхождение, в котором на j-том месте расхождения) было число, на которое нужно было вернуться назат (с j- того места) для нового сравнения (возможно и “-1”, т.е. идти вперёт).

Вычисление D само является поиском в строке, для чего можно использовать КМП алгоритм.

Алгоритм: а) вычисление таблицы D

б) ищем вхождение первого элемента

в) поэлементно сравниваем, если не совпадает на j-той позиции → подставляем j в таблицу D и продолжаем проверять, сдвинув начало первого вхождения на j – d[j]

г) если в строке ещё может быть слово (j!= Н – М) возвращаемся к п.б, ELSE – вхождений нет.

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

Минус – подлинный выигрыш только, если перед неудачей было некоторое число совпадений (скорее исключение, чем правило).

 

35 Алгоритм Бойера-Мура.. Р.Боер и Д.Мур предложили алгоритм, который не только улучшал (относительно КМП) обработку самого худшего случая (когда в образце и строке многократно повторяется не большое число букв), но и даёт выигрыш в промежуточных ситуациях.

БМ алгоритм поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

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

Если символы совпадают, производится сравнение предпоследнего символа шаблона и т.д.

Если все символы образца совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ образца не совпадает с соответствующим символом строки, шаблон сдвигается на “несколько”символов вправо, и проверка снова начинается с последнего символа (эти “несколько” обычно равно разнице между [количеством литеров в образце] и [первой встречи (справа) данного символа в образце]).

Достоинствами БМ является то, почти всегда, кроме специально построенных случаев, он требует значительно меньше Н сравнений, проходя “саженью образа” по строке. Лучшая оценка, когда последний символ образа всегда не совпадает с соответствующими литерами строки, проходимой аршином М, равно Н/М.

В своей публикации (которая была после Кнута, Морриса и Пратта) Боер и Мур приводили соображения о дальнейшем улучшение алгоритма. Одно из которых – объединение стратегий БМ (больший сдвиг во время несовпадений) и КМП (существенный сдвиг при частичном совпадение), которая основывалась на 2х таблицах, из которых выбиралось большее смещение.

36 Алгоритм Рабина-Карпа. Разработанный в 1987 году М. Рабином и Р.Карпом алгоритм поиска подстроки эффективен на практике и обобщаем для многомерного случая (например, поиск в 2мерном массиве).

Хотя в худшем случае время работы составляет O (M * (N – M + 1)), в среднем он работает достаточно быстро.

Идея: без ограничения общности предположим, что алфавит строки и образца – цифровой (а строки имеют простую цифровую интерпретацию).

Если p[0 … M – 1] – образец, то число Р – десятичная запись образца.

В последовательности s[0 … n – 1] через числа Sj (для всех j от 0 до N – M – 1) обозначим десятичное представление всех последовательностей s[j … j + M – 1] (длина такой подстроки равно длине образца)

Р вычисляется по схеме Горнера: Р = р[M – 1] + 10(р[M – 2] + 10(… + 10(p1 + 10 * p0) …))

Если известна Sj, то вычисление S[j+1] есть вычёркивание первой цифры в Sj и приписывание в конец s[j+M]: S[j+1] = 10(Sj – 10^(m-1) * sj) + s[j+M]

Если Sj = Р, то Sj – вхождение образца в строку.

{числа бывают огроменные (не влезают ни в один тип) → вычисляем не сами Р и S, а их остаток от деления на простое число q, такое, чтобы для алфавита {0, 1, …, d} число dq помещалось в машинное слово, т.е.

S[j+1] = (d(Sj – h * sj) + s[j+M]) mod q, h = d^M-1}

 

Таблицы с прямым доступом.

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

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

{для такого финта ушами нужно поместить таблицу с массив (доступ за постоянное время)}

Для этого перевода нужна хеш-функция (отображение H ключей элементов в адреса памяти).

Простейший пример хеш-функции: функция получения числового кода литера

(если литеров несколько, то можно воспользоваться схемой Горнера: А = б + (i – 1) * sizeof(T), где б – адрес начала массива, i – индекс компоненты вектора, отсчитываемый от “1”, sizeof(T) – размер компоненты вектора).

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

На такой случай нужно предусмотреть операцию рехеширования – переадресация, в случае занятости адреса (запись нового элемента) или в случая, когда по данному адресу находится элемент с другим ключом (чтение).{2 способа:

организовать список строк с идентичным первичным ключом H(k) (этот список может расположить где душе угодно, но такой способ вызовет увеличение расхода памяти);

или, при занятости данной ячейки памяти, “впихнуть” наш элемент куда-нибудь рядом}

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

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

38 Алгоритмы сортировки. Сортировка называется устойчивым (стабильным), если в процессе сортировки относительное расположение элементов с равными ключами не изменилось.

Характеристики методов сортировки

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(nlogn) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n).

Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных.

Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

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

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

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

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов).

Категория сортировок входящие в раздел “внутренние” имеют прямые методы сортировок.

Сортировка вставкой (устойчивая). Вставка элемента в на нужную позицию в уже отсортированном массиве.

Сортировка выборокой (не устойчивая). 1-ый элемент меняется местами с минимальным, далее 2-ой так же..

Пузырьковая сортировка. 1-ый элемент сравнивается с соседним, если >, то меняются местами, если <, то берется тот элемент с кем происходило сравнение и сравнивают его, так пока не дойдем до конца. В 1-ой итерации всегда всплывет максимальный элемент.

Сортировка Шелла. Выбирается интервал d, через которые будут сравниваться элементы в первый проход, к примеру 5, после полного прохода, берется новый интервал 3 и опять проход и так далее.

Турнирная сортировка.

 

39 Сортировка вставкой. Преимущества данного алгоритма:

1)эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

2)эффективен на наборах данных, которые уже частично отсортированы;

3)это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

4)может сортировать список по мере его получения;

5)использует 0(1) временной памяти, включая стек.

Минусом же является высокая сложность алгоритма: 0(n^2).

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

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

{т.е. у нас есть 2 части массива: отсортированная и не отсортированная}

{массив из одного или нуля элементов отсортирован!}

 

сложность O(n^2)

Вход: массив A, состоящий из элементов A[1], A[2],..., A[n]

 

for i = 2, 3,..., n:

key:= A[i]

j:= i - 1

while j > 0 and A[j] > key:

A[j + 1]: = A[j]

j:= j - 1

A[j + 1]: = key

40 Сортировка выборкой. Алгоритм сортировки может быть реализован и как устойчивый и как неустойчивый. На массиве из п элементов имеет время выполнения в худшем, среднем и лучшем случае О(n^2), предполагая что сравнения делаются за постоянное время. Шаги алгоритма:

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

2.(только 8 устойчивых реализациях) если значения элементов неравны, то;

3.производим обмен этого значения со значением первой не отсортированной позиции;

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

Пример:

void selectSort(T a[], long size) {

long i, j, k;

T x;

for(i=0; i < size; i++) { // i - номер текущего шага

k=i; x=a[i];

for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента

if (a[j] < x) {

k=j; x=a[j]; // k - индекс наименьшего элемента

}

a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]

}

}

 

42 Сортировка Шелла. Первое улучшение алгоритма заключается в запоминании, производился и на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

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

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

Выигрыш Шелла в том, что на каждом шаге либо сортируется мало элементов, либо они досортировываются.

Недостатки – не устойчивость и сложны математический анализ (до сих пор не найдена универсальная последовательность шагов, дающая минимальную сложность). Сложность O (n ^ (1+б)), где б от “0” до “1”, что хуже, чем n * lnn

Турнирные сортировки.

В сортируемом множестве можно сравнить пары соседних элементов → из n/2 сравнений получаем меньшую по значению ключей половину (победители); также из получаем четверть и т.д., пока не получим один элемент.

Результат – дерево выбора (турнирная таблица – двоичное дерево, в котором для каждого двудутного узла один из сыновей – он сам (победитель), а другой больше своего отца) (в корне – самый маленький элемент)

Перевода в множество: а) возьмём корень и запишем его в множество

б) спускаемся от победителя к призёрам по пути победителя, опустошая вершины

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

г) теперь место победителя занял новый элемент; переходим к п.1

Достоинство – сложность всегда О(n * lnn).

{для уменьшения расхода памяти необходимо применить пирамидольное улучшение традиционных древовидных сортировок (hi =<h2ihi =<h[2i+1]); в пирамиде нет повторов элементов сортируемого множества}

Строительство пирамиды: 1) первоначально элемент помещается в вершину, i = 0

2) рассмотрим тройку элементов с индексами i, 2i, 2i+1 (узел и его дети)

3) выберем наименьший из п.2: если он на позиции i, элемент вставлен; ELSE обозначим позицию наименьшего буквой j, где j=j2i или j = 2i + 1, меняем местами элементы i и j

4) переходим к п.2

 

44 Сортировка Хоара. Быстрые сортировки – те, в которых осуществляются перестановки на большие расстояния. Алгоритм:.

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

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

Рассмотрим пример: Дано множество {9,6,3,4,10,8,2,7}.

Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно, элементы меняются местами. >> {7,6,3,4,10,8,2,9}.

Далее начинаем последовательно сравнивать элементы с 9, и менять их местами в зависимости от сравнения. {7,6,3,4,10,8,2,9} >> {7,6,3,4,10,8,2,9}>>{7,6,3,4,10,8,2,9}>> {7,6,3,4,9,8,2,10} - 9 и 10 меняем местами. >> {7,6,3,4,8,9,2,10} - 9 и 8 меняем местами. >> {7,6,3,4,8,2,9,10} - 2 и 9 меняем местами..

После такого перебрасывания элементов весь массив разбивается на два подмножетсва, разделенных элементом 9. >>{7,6,3,4,8,2} {10}.

Далее по уже отработанному алгоритму сортируются эти подмножества. Подмножество из одного элемента естественно можно не сортировать.Выбираем в первом подмножестве базовый элемент 7. >>{7,6,3,4,8,2} >> {2,6,3,4,8,7}-меняем местами 2 и 7>>{2,6,3,4,8,7}>>{2,6,3,4,8,7}>>{2,6,3,4,8,7}>>{2,6,3,4,7,8}-меняем местами 7 и 8

Получили снова два подмножества: {2,6,3,4} {8}.

Достоинства – легко распаралеливается, что полезно в нашь век многопроцессорных/ядерных/потоковых ЭВМ.

(лучший случай - когда каждыё раз медиана выбирается зерном).

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

Недостаток – плохо работает при малых n (в прочем, как и все усовершенствованные методы)

45 Сортировки слиянием Решения задачи сортировки:

1) последовательность а разбивается на 2 половины b и c

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

3) два упорядоченных массива половинного размера соединяются в один.

4) части b и c сливаются; при этом одиночные элементы из разных частей образуют упорядоченные пары в выходной последовательности, т.е. первым в ней оказывается меньший из 2х первых элементов

5) полученная последовательность более упорядочена чем изначальная и она снова подвергается разделению и слиянию; при этом упорядоченные пары переходят в четверки, те – в 8ки и т.д..

Пример(МОЙ!!): (40 47 10 38 80 20 01 50)→(40 47 10 38) (80 20 01 50) →(40 80 20 47 01 10 38 50) →(40 80 20 47)(01 10 38 50) →(01 10 40 80 20 38 47 50) →(01 10 40 80)(20 38 47 50) →(01 10 20 38 40 47 50 80)