- •Сортировки
- •Введение
- •Формулировка задачи сортировки
- •Простейшие методы сортировки
- •Алгоритм линейной сортировки (метод прямого выбора)
- •1 Способ 2 способ
- •Алгоритм сортировки обменом (метод "Пузырька")
- •Усовершенствованная "пузырьковая" сортировка
- •"Шейкер" - сортировка
- •Сортировка подсчетом
- •Алгоритм сортировки вставками (метод прямого включения)
- •Размещение путем сравнения и обмена (просеивание)
- •Размещение путем поиска места и вставки
- •Более сложные и более эффективные методы сортировки
- •Алгоритм сортировки Шелла (метод h-сортировки)
- •Обменная сортировка с разделением (сортировка Хоара)
- •Сортировка методом слияний
- •Простое слияние
- •Естественное двухпутевое слияние
- •Рекурсивный алгоритм слияния
- •Слияние списков
- •Алгоритм сортировки бинарными вставками
- •Сортировка с помощью двоичного включения
- •Лексикографическая сортировка
- •Топологическая сортировка
- •Поразрядная сортировка
- •Пирамидальная сортировка
- •Рекурсивная сортировка
- •Сравнительная характеристика методов сортировки
- •Классификация задач с применением сортировок
- •1. Задачи заполнения
- •2. Задачи анализа
- •3. Задачи поиска
- •4. Задачи перестановки
- •Литература
Алгоритм сортировки бинарными вставками
Место, соответствующее некоторому элементу массива в предшествующей ему последовательности, можно найти значительно быстрее, пользуясь тем, что эта последовательность уже упорядочена.
Для этого необходимо использовать так называемый бинарный поиск, который исследует средний элемент упорядоченной последовательности и продолжает деление пополам, пока не будет найдено место включения.
Разработаем функцию 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] не приводит к увеличению продолжительности сортировки. В то же время если такую проверку не проводить, то в случаях, когда исходный массив упорядочен или близок к таковому, бинарный поиск потребует большего времени, чем методы поиска, описанные в начальных пунктах данного параграфа!
Этот пример показывает, что в ряде случаев "очевидное улучшение" программ оказывается намного менее существенным, чем кажется вначале, а иногда может на самом деле оказаться ухудшением.