Алгоритмы поиска и сортировки данных — это алгоритмы обработки определённого множества данных для выявления подмножества данных, которое соответствует критериям поиска.
Введение
Сегодня написание программ для компьютерной техники является не только средством, грамотное использование которого играет решающую роль в результативной работе практически во всех прикладных сферах, но также и сферой научного исследования. Очевидно, что знание алгоритмов имеет очень большое значение для формирования решений о структурировании данных. Потоки всевозможной информации постоянно возрастают.
Для того, чтобы сохранить различную информацию применяются специальные базы данных. Причём данные базы, если в них хранится огромное количество компонентов, использовать достаточно сложно, фактически нереально. Не потерять в таком объеме необходимые данные без использования сортировки также практически невозможно. Сортировка данных позволяет относительно быстро и качественно выделить необходимую информацию из предварительно упорядоченных информационных наборов. Это означает, что алгоритмы сортировки обладают очень важным значением, особенно при обработке информации. В сфере программирования уделяется значительное внимание методикам сортировки и их алгоритмизации.
На данный момент существует большое количество алгоритмов сортировки, которые имеют различный характер и скорость информационной обработки. Однако многие из них обладают достаточно существенным недостатком, а именно, период их выполнения пропорционален квадрату количества компонентов.
Алгоритмы поиска и сортировки данных
Алгоритмом является любая корректно представленная вычислительная процедура, на входе, которой задано какое-либо значение или набор значений, а результатом её выполнения выступает выходное значение или набор значений. То есть, алгоритмом является определенная очерёдность вычислительных операций, преобразующих входные значения в выходные.
Алгоритм может быть представлен и как инструмент, при помощи которого могут решаться правильно сформулированные вычислительные задачи. Алгоритм призван описать определённый вычислительный процесс, при помощи которого возможно достичь реализации указанных отношений.
Наиболее известным и простым считается алгоритм последовательного поиска. Этот алгоритм выполняет просто поочередное сравнение всех элементов выбранного списка с ключом поиска до того момента, пока не будет найден элемент с необходимым значением ключа, когда поиск является удачным, или пока полностью список не будет проверен, но требуемый элемент не был обнаружен, в случае неудачного поиска. Иногда используется достаточно несложный добавочный способ, когда добавляется ключ поиска в самый конец списка, в этом случае поиск безоговорочно превратится в успешный. Это позволяет удалить контроль окончания списка при любой итерации алгоритма. Ниже приведён псевдокод такого усовершенствованного варианта. Возможно представление исходных данных в виде массива.
Алгоритм SequentialSearch2 (А[0..n], К)
// Алгоритм осуществляет последовательный поиск с применением
// ключа поиска как ограничителя
// Начальные данные: Массив А из n компонентов и ключ поиска К
// Выходные данные: Позиция первого компонента массива A[0..n – 1],
// значение у которого такое же, как и с К; если компонент не был обнаружен,
// возвращается значение –1
А[п] = К
i = 0
while А[i] K
i = i + 1
if i
return i
else
return –1
Бинарным поиском является в высшей степени эффективный алгоритм, который применяется при поиске в отсортированном массиве. Данный алгоритм функционирует по методу сравнения нужного ключа К со средним элементом массива А[m]. В случае равенства, алгоритм выполняет завершение поиска. В противном случае эта же операция рекурсивно исполняется для начальной половины массива, если К ∠ А[m], и для другой половины, если К > А [m].
Ещё одним алгоритмом поиска является поиск подстроки. Задачи поиска подстроки может быть сформулирована следующим образом. Задана символьная строка длиной n, называемая текстом, и строка длиной т (т n), которая называется шаблоном (pattern). Необходимо найти в тексте подстроку, соответствующую шаблону. Иными словами, необходимо найти i, которое является индексом самого левого символа первой подходящей шаблону подстроки в тексте. Если необходимо найти все подобные подстроки, то алгоритм поиска подстроки следует повторять до окончания проверки всего текста.
Далее рассмотрим алгоритмы сортировок. Сортировкой является операция упорядочения объектов определённого множества данных в заданном порядке. Главной целью процесса сортировки является повышение скорости дальнейшего поиска значений в отсортированном информационном массиве. Фактически почти в любой задаче могут присутствовать компоненты сортировки. Прошедшие сортировку компоненты имеются в телефонных справочниках, в оглавлениях, в библиотеках, в словарях, и во многих других местах их использования.
Очевидно, что существует определённая зависимость выбора алгоритмов сортировки от структуры данных. Используемые методики сортировки могут быть поделены на следующие группы:
- Методы сортировки файлов.
- Методы сортировки массивов.
Эти две группы часто представляются как внутренняя и внешняя сортировка, поскольку массивы располагаются во «внутренней» (оперативной) памяти компьютерного оборудования, а изучаемые файлы располагаются в не очень быстрой, но существенно более вместительной «внешней» памяти.
Главными признаками эффективности алгоритмов сортировки являются следующие параметры:
- Параметр быстродействия.
- Параметр экономии памяти.
- Параметр сокращения времени, которое затрачивается программистом, на выполнение алгоритма.
Поэтому в зависимости от числа компонентов множества, их упорядоченности, частоты использования сортировки и иных факторов, необходимо применять разные алгоритмы сортировки и поиска.
