Лекция. Алгоритмы сортировки Под сортировкой


Простая сортировка вставками



бет2/5
Дата03.12.2023
өлшемі0,94 Mb.
#134200
түріЛекция
1   2   3   4   5
Байланысты:
Алгоритмы сортировки

Простая сортировка вставками

Этот метод часто используется игроками в карты. Элементы (карты) мысленно разделяются на последовательность-приемник a0 ... ai–1 и последовательность- источник ai ... an–1. На каждом шаге, начиная с i=1 и затем увеличивая i на единицу, в последовательности-источнике берется i-й элемент и ставится в правильную позицию в последовательности-приемнике. В табл. 2.1 работа сортировки вставками показана на примере восьми взятых наугад чисел. Алгоритм простых вставок имеет вид
for (i = 1;i<= n–1;i++)
{ x = a[i];
вставить х в правильную позицию среди a0 ... ai–1
}


При поиске правильной позиции для элемента удобно чередовать сравнения и пересылки, то есть позволять значению x «просеиваться» вниз, при этом сравниваем x со следующим элементом aj, а затем либо вставляем x, либо передвигаем aj вправо и переходим влево. Заметим, что есть два разных условия, которые могут вызвать прекращение процесса просеивания:
1. У элемента aj ключ оказался меньше, чем ключ x.
2. Обнаружен левый конец последовательности-приемника.
// StraightInsertion
int i, j, x;
for (i= 1; i<=n–1;i++)
{ x= a[i]; j = i;
while ((j > 0) & (x < a[j–1]))
{ a[j] := a[j–1]; j++;
}
a[j]= x;
}
Анализ простой сортировки вставками. Число сравнений ключей в i-м просеивании Ci не больше i–1, как минимум равно 1 и – предполагая, что все перестановки n ключей равновероятны, – в среднем равно i/2. Число Mi пересылок (присваиваний элементов) равно Ci+1. Поэтому полные числа сравнений и пересылок равны
Cmin = n–1 Mmin = 2*(n–1)
Cave = (n2–n)/4 Mave = (n2+3n–4)/4
Cmax = (n2–3n+2)/2 Mmax = (n2–n)/2

Этот алгоритм нетрудно усовершенствовать, заметив, что последовательность-приемник a0 ... ai–1, в которую нужно вставить новый элемент, уже упорядочена. Поэтому можно использовать более быстрый способ нахождения позиции вставки. Очевидный выбор – алгоритм деления пополам, в котором проверяется середина последовательности-приемника и затем продолжаются деления пополам, пока не будет найдена точка вставки. Такой модифицированный алгоритм называется сортировкой двоичными вставками:


// BinaryInsertion;
int i, j, m, L, R, x;
for (i = 1; i<= n–1; i++)
{ x = a[i]; L = 0; R = i;
while (L < R)
{ m = (L+R) div 2;
if (a[m] <= x) L = m+1;
else R = m;
}
for (j = i; j>= R+1; j--)
a[j] = a[j–1];
a[R] = x;
}


Достарыңызбен бөлісу:
1   2   3   4   5




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет