КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритм 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; Просмотров: 1210; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |