Метод прямых вставок с барьером
Чтобы сократить количество сравнений в алгоритме прямых вставок, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент. В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х.Реализация алгоритма прямых вставок с барьером на паскале:
for i:= 2 to N do
if a[i-1]>a[i] then
begin
a[0]:= a[i];
j:= i-1;
while a[j]>a[0] do
begin
a[j+1]:= a[j];
j:= j-1;
end;
a[j+1]:= a[0];
end;
for i:= 2 to N do
if a[i-1]>a[i] then
begin
a[0]:= a[i];
j:= i-1;
while a[j]>a[0] do
begin
a[j+1]:= a[j];
j:= j-1;
end;
a[j+1]:= a[0];
end;
Эффективность алгоритма.
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм совершит
Ø N-1 сравнение
Øи 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" будет
Øсравнений (N+1)*N/2,
Øа пересылок (N-1)*(N+3).
Таким образом, этот алгоритм имеет сложность О(N2) по обоим параметрам.
Тэги: прямые вставки, прямые вставки с барьером, алгоритм прямых вставок.
Тэги: прямые вставки, прямые вставки с барьером, алгоритм прямых вставок.