Задача информационного поиска. Алгоритмы нахождения номера элемента с заданным значением в последовательности из различных элементов.
Пусть задана последовательность {Xi} = Х1, Х2,..., XN, где i изменяется от 1 до N. По условию в последовательности {Xi} все элементы имеют разные значения. Необходимо определить номер элемента, значение которого равно значению некоторой заданной переменной Р. Причем в заданной последовательности может не оказаться элемента со значением Р. Первая ситуация - упорядоченная последовательность.
Основной алгоритм поиска имеет следующий вид:
a. Сравнить очередной элемент с переменной Р.
b. Перейти к следующему элементу.
c. Если не все элементы просмотрены, то повторить с п. а.
Алгоритм должен однозначно реагировать на ситуацию, если искомого значения в последовательности нет. Введем переменную k с начальным значением, равным 0. Результат k - номер найденного элемента.
Если элемент со значением Р не найден, то результат k остается нулевым (рис. 1.13). Если последовательность упорядочена, т. е. значения элементов последовательности возрастают или убывают с увеличением порядковых номеров (индексов) элементов, то к ней можно применить другой алгоритм поиска. В процессе поиска можно сдвинуть друг к другу границы промежутка, в котором после каждого сравнения сдвигается либо верхняя, либо нижняя граница. Алгоритм, в котором последовательно уменьшается промежуток исследуемых данных в два раза, называется алгоритмом дихотомии - деление отрезка пополам.
Пусть значение наименьшего элемента исходной последовательности равно А, а значение наибольшего элемента - В. Если разделить рассматриваемый интервал [А, В] пополам, то получится некоторое значение С. Сравнить С с заданным значением Р. Повторять эти действия до тех пор, пока А и В не совпадут. Проверить условие Х[А] = Р. По результатам проверки должен быть сформирован результат.
|
|
Схема алгоритма поиска заданного элемента
Словесный алгоритм поиска имеет следующий вид:
a. Вычислить С.
b. Сравнить Х[С] с переменной Р.
c. Определить А и В.
d. Если А и В не совпадают, то повторить с п. а.
e. Проверить совпадение выделенного значения с поисковой Р.
Задача сортировки массивов. Алгоритм простого выбора.
Алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
находим минимальное значение в текущем списке
производим обмен этого значения со значением на первой неотсортированной позиции
теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Сортировка массивов. Алгоритм Шелла.
Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.
|
|
Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i – h], A[i – 2h], A[i – 3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h-серии» элементов, отстоящие друг от друга на h, сортируются отдельно. Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h = 1.
