Алгоритм 2. Сортировка простым включением

Суть алгоритма. На каждом шаге, начиная с K=2, берем K-ый элемент и вставляем его на подходящее место в левой части. Этот алгоритм удобнее реализовывать с помощью списковых структур.

Алгоритм 3. Сортировка обменом (метод пузырька).

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

Схема алгоритма сортировки обменом приведена на рис.3.11.4.

Рис.3.11.4.

В алгоритме используются следующие переменные:

N – количество обрабатываемых элементов массива Y;

PG – динамическая верхняя граница массива;

KP – счетчик перестановок;

K – счетчик элементов массива;

X – переменная, через которую осуществляется перестановка элементов массива.

Циклический процесс сравнения соседних элементов включает в себя блоки 4 – 7. После выхода из цикла верхняя граница (PG) уменьшается на 1 и проверяется значение счетчика KP.

3.12.3. Поиск данных

При поиске данных предполагается, что искомая информация хранится в записях, которые можно идентифицировать значениями ключей, то есть записи Zi соответствует значение ключа Ki. Если в качестве ключей используются целые числа, то задача сводится к поиску значения в числовом массиве. Пусть в массиве MP случайным образом расположены N чисел. Тривиальный алгоритм – поиск путем последовательного просмотра ключей требует слишком много операций. Время поиска можно заметно уменьшить, если предварительно упорядочить файл по ключам и применить алгоритм дихотомического поиска (его также называют алгоритмом двоичного поиска). Эта предварительная сортировка имеет смысл, если файл достаточно велик и к нему обращаются часто.

Рис.3.11.5.

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

Схема алгоритма дихотомического поиска приведена на рис.3.11.5. На рис.3.11.5 обозначено:

L – левая граница массива;

P – правая граница массива;

N – количество обрабатываемых элементов в массиве;

S – номер среднего элемента;

PZ – признак завершения алгоритма: PZ=0 – решение найдено; PZ=1 – искомого значения нет массиве.

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