Алгоритмы поиска и сортировки данных

Введение

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

Для того, чтобы сохранить различную информацию применяются специальные базы данных. Причём данные базы, если в них хранится огромное количество компонентов, использовать достаточно сложно, фактически нереально. Не потерять в таком объеме необходимые данные без использования сортировки также практически невозможно. Сортировка данных позволяет относительно быстро и качественно выделить необходимую информацию из предварительно упорядоченных информационных наборов. Это означает, что алгоритмы сортировки обладают очень важным значением, особенно при обработке информации. В сфере программирования уделяется значительное внимание методикам сортировки и их алгоритмизации.

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

Алгоритмы поиска и сортировки данных

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

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

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

Алгоритм 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, которое является индексом самого левого символа первой подходящей шаблону подстроки в тексте. Если необходимо найти все подобные подстроки, то алгоритм поиска подстроки следует повторять до окончания проверки всего текста.

Далее рассмотрим алгоритмы сортировок. Сортировкой является операция упорядочения объектов определённого множества данных в заданном порядке. Главной целью процесса сортировки является повышение скорости дальнейшего поиска значений в отсортированном информационном массиве. Фактически почти в любой задаче могут присутствовать компоненты сортировки. Прошедшие сортировку компоненты имеются в телефонных справочниках, в оглавлениях, в библиотеках, в словарях, и во многих других местах их использования.

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

1. Методы сортировки файлов.
2. Методы сортировки массивов.

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

Главными признаками эффективности алгоритмов сортировки являются следующие параметры:

1. Параметр быстродействия.
2. Параметр экономии памяти.
3. Параметр сокращения времени, которое затрачивается программистом, на выполнение алгоритма.

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