Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2021-01-29 | 73 |
5.00
из
|
Заказать работу |
|
|
Место, соответствующее некоторому элементу массива в предшествующей ему последовательности, можно найти значительно быстрее, пользуясь тем, что эта последовательность уже упорядочена.
Для этого необходимо использовать так называемый бинарный поиск, который исследует средний элемент упорядоченной последовательности и продолжает деление пополам, пока не будет найдено место включения.
Разработаем функцию Binary_Search, определяющую индекс ячейки в упорядоченной части массива а, в которой должно размещаться некоторое число т.
Упорядоченная часть массива имеет границы индексов 1..last.
Обозначим l — индекс левого элемента исследуемого в холе поиска отрезка массива, r — правого, mid — величину, равную (1+r)/2. В начале поиска принимаем l =1, r=last.
Определяем величину mid и сравниваем значения: a[mid] и т.
Если a[mid] >m, то размещаемое число должно находиться в левой половине исследуемого диапазона, т. е. можно принять r=mid-1, в противном случае — в правой половине — 1=mid+1.
После этого процесс повторяется применительно к новому диапазону и заканчивается, когда r станет меньше 1. В этой ситуации искомый индекс равен значению 1.
При разработке функции на Паскале следует учесть, что в этом языке использование массивов с переменными границами не допускается. Поэтому придется использовать в числе параметров функции величину а типа arrtype:
function Binary_Search(last:word;var a:arrtype;m:word):word;
var l,r,mid:word;
begin
j:=1;
r:=last;
while 1<=r do
begin
mid:=(l+r) div 2;
if a[mid]>m then r:=mid-1
else l:=mid+1
end;
Binari_Search:=l;
end;
Процедуры сортировки методом бинарных вставок, использующие приведенные функции, имеют вид:
procedure Binary_Insert_Sort(var a:arrtype);
var i:integer;
begin
|
for i:=2 to n do
if a[i]<a[i-l] then Insert(a,i,Binary_Search(i-l,a,a[i]))
{Вставляем элемент a[i] на его место,
найденное методом бинарного поиска
на отрезке массива а с индексами от 1 до i-1}
end;
Разновидность метода вставок, использующая бинарный поиск места размещения очередного элемента, называется сортировкой бинарными вставками.
Сравним ее с вариантами, описанными выше (эти варианты сортировки носят название "метод простых вставок").
Когда при сортировке простыми вставками на соответствующем месте размещается 1-й элемент, то его значение сравнивается в среднем примерно с i/2 ранее отсортированными значениями; поэтому общее, число сравнений при этом равно (1+2+...+n) /2=n2/4, а это очень много, даже если n умеренно велико».
При использовании же бинарного поиска места размещения очередного элемента число сравнений значительно меньше. Например, если очередной элемент — 64-й, то его значение сначала сравнивается с 32-м; затем с 16-м или 48-м и т. д., так что искомое место будет найдено максимум после всего лишь шести сравнений. Общее же число сравнений для n элементов равно приблизительно nlog2n, что существенно лучше, чем n2 /4;
Неприятность состоит в том, что бинарный поиск решает только половину задачи — после того, как мы нашли место очередного элемента, все равно нужно "вставить" этот элемент на найденное место и сместить некоторый отрезок упорядоченной последовательности на 1 позицию вправо.
А поскольку в компьютере операция присваивания выполняется за значительно большее время, чем операция сравнения, то общая экономия времени будет незначительной, так что общее время работы при бинарном поиске, по существу, остается пропорциональным п2/2.
Это подтверждают и расчеты (табл. 4). Хотя для вещественных чисел сравнение выполняется медленнее, чем присваивание.
Таблица 4. Сравнительная характеристика методов
простых вставок и бинарных вставок
Метод | Количество элементов в массиве | ||
n=1000 | n=2000 | n=4000 | |
Простые вставки | 1,2 | 4,5 | 19,0 |
Бинарные вставки | 1,0 | 3,5 | 14,2 |
|
Интересным является вопрос о том, стоит ли перед размещением очередного элемента проверять, меньше ли он предшествующего элемента (в представленных процедурах такая проверка проводится).
Как показали расчеты, проверка условия a[i]<a[i-l] не приводит к увеличению продолжительности сортировки. В то же время если такую проверку не проводить, то в случаях, когда исходный массив упорядочен или близок к таковому, бинарный поиск потребует большего времени, чем методы поиска, описанные в начальных пунктах данного параграфа!
Этот пример показывает, что в ряде случаев "очевидное улучшение" программ оказывается намного менее существенным, чем кажется вначале, а иногда может на самом деле оказаться ухудшением.
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!