Реферат Курсовая Конспект
Алгоритм 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 – искомого значения нет массиве.
– Конец работы –
Эта тема принадлежит разделу:
Алгоритм Сортировка простым включением... Суть алгоритма На каждом шаге начиная с K берем K ый элемент и вставляем... Алгоритм Сортировка обменом метод пузырька Схема алгоритма...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм 3. Сортировка обменом (метод пузырька).
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов