Сортировка и поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе.

Основная задача поиска — найти элемент, удовлетворяющий некоторым условиям.

Классификация алгоритмов поиска. Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность.

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

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

Поиск в колоде карт – поиск по истинным ключам, то есть имеете дело с тем, что есть. Поиск в словаре – поиск по преобразованным ключам, так как все слова отсортированы в алфавитном порядке, то есть массив значений изменен перед началом поиска. Этот порядок создан специально для облегчения поиска и вовсе не является естественным для списка слов.

Третий вариант классификации – методы основанные на сравнении самих значений и методы, основанные на их цифровых свойствах. Так называемые методы хэширования.

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве. Следовательно, методы сортировки важны особенно при обработке данных.

Зависимость выбора алгоритма от структуры данных — явление довольно

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

Алгоритмы сортировки массивов можно разбить на три класса:

1) сортировка включениями;

2) сортировка выбором;

3) сортировка обменом.

Дата добавления: 2014-01-20