Вопрос 4: «Поиск. Оптимальность поиска. Статические и динамические методы поиска. Ключ. Метод дихотомии. Оценки алгоритмов поиска»

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

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

Оценки алгоритмов поиска:

1. Время

2. Память

3. Устойчивость (не меняет местами равные элементы)

4. Естественность поведения – эффективность метода при обработке уже отсортированных частично данных

Вопрос 5: «Сортировка. Методы сортировка в простейших задачах»

Сортировка - это алгоритмический процесс перестановки объектов данного множества в определённом заданном порядке. Цель сортировки - это облегчение последующего поиска элементов в отсортированном множестве. Основное требование к методам сортировки массивов - это экономное использование памяти. Другими словами, переупорядочивание элементов необходимо выполнять "на том же месте", а методы, которые пересылают элементы из массива A в массив B, не представляют интереса.

Сортировка выбором

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

Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:

(а) минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.

Сортировка обменом

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

Сортировку обменом называют ещё "пузырьковой сортировкой" (в силу очевидного сравнения с всплытием пузырьков воздуха в жидкости).

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

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

Для сортировки включениями необходима вспомогательная процедура, которая обеспечивает перемещение элемента с индексом i на место элемента с индексом j и смещение всех элементов с индексами от j до i-1 на одну позицию вправо.