Алгоритмы поиска и сортировки данных
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
овке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Работа алгоритма проиллюстрирована на рис. 2.5.
Рис. 2.5. Пример сортировки методом Шелла
Псевдокод данного алгоритма.
Алгоритм ShellSort (А [0..n - 1])
// Сортировка массива подсчетом Шелла
// Входные данные: Массив А[0..n - 1] упорядочиваемых значений
// Выходные данные: Массив А[0..n - 1] элементов отсортированных
// в неубывающем порядке
d = n
while d > 1
d = d / 2= 0(j = i + d) А[j]
обмен А[i] и А[j]
i++
Вызов метода сортировки пузырьком или сортировки вставками или сортировки выбором.
Последовательный поиск:
Этот алгоритм просто по очереди сравнивает элементы заданного списка с ключом поиска до тех пор, пока не будет найден элемент с указанным значением ключа (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск). Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен псевдокод такой улучшенной версии; предполагается, что входные данные имеют вид массива.
Алгоритм SequentialSearch2 (А[0..n], К)
// Алгоритм реализует последовательный поиск с использованием
// ключа поиска в качестве ограничителя
// Входные данные: Массив А из п элементов и ключ поиска К
// Выходные данные: Позиция первого элемента массива A[0..n - 1],
// значение которого совпадает с К; если элемент не найден,
// возвращается значение -1
А[п] = К
i = 0
while А[i] K= i + 1i < пi
return -1
Если исходный список отсортирован, можно воспользоваться еще одним усовершенствованием: поиск в таком списке можно прекращать, как только встретится элемент, не меньший ключа поиска.
Бинарный поиск:
Бинарный поиск представляет собой в высшей степени эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа К со средним элементом массива А[m]. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если К А [m].
В качестве примера найдем ключ К = 70, применяя алгоритм бинарного поиска к массиву. Пример показан на рисунке 2.6
алгоритм сортировка программирование поиск
Рис. 2.6. Пример бинарного поиска
Хотя ясно, что бинарный поиск основан на рекурсии, его очень легко реализовать как нерекурсивный алгоритм. Вот псевдокод нерекурсивной версии
АЛГОРИТМ Binary Search (А[0..п - 1], К)
// Реализует нерекурсивный бинарный поиск
// Входные данные: Массив А[0..п - 1], отсортированный
// в возрастающем порядке, и искомый ключ К
// Выходные данные: Индекс элемента массива, равного К,
// или -1, если такого элемента нет
l = 0;
r = n - 1
while l r do
т = ;К = А[т]mif К < А[т]= m - 1
r = m + 1
return -1
Стандартный способ анализа эффективности бинарного поиска состоит в подсчете количества сравнений искомого ключа с элементами массива. Кроме того, из соображений простоты, мы будем считать, что используются тройные сравнения, т.е. что одно сравнение К и А[m] позволяет определить, меньше ли К, больше или равно значению А[m].
Сколько же сравнений должен выполнить алгоритм при поиске в массиве из n элементов? Ответ, очевидно, зависит не только от n, но и от конкретного экземпляра задачи. Найдем количество сравнений в наихудшем случае. В наихудший случай входят все массивы, которые не содержат искомого ключа (кроме них в этот разряд попадают и некоторые массивы, поиск в которых завершается успешно).
В частности, потребуется не более чем 10 тройных сравнений для поиска элемента с заданным значением (или выяснения того, что такой элемент отсутствует) в массиве из 1000 элементов, и не более 20 сравнений для поиска в массиве в миллион элементов.
Поиск подстроки:
Описание задачи поиска подстроки: дана символьная строка длиной п, называющаяся текстом, и строка длиной т (т п). именуемая шаблоном (pattern); требуется найти в тексте подстроку, соответствующую шаблону. Говоря точнее, нужно определить i - индекс крайнего слева символа первой соответствующей шаблону подстроки в тексте.
Если требуется найти все такие подстроки, алгоритм поиска подстроки может просто продолжать работу до полной проверки текста.
Алгоритм, основанный на грубой силе, очевиден: шаблон выравнивается с началом текста и по очереди сравниваются соответствующие пары символов слева направо до тех пор либо символы во всех т парах будут равны (в этом случае алгоритм может прекращать работу), либо не встречается пара разных символов. В ?/p>