Вторник, 19.03.2024, 12:38
Приветствую Вас, Гость |
Меню сайта
Наш опрос
Нужен ли форум на этом сайте?
Всего ответов: 1296
Статистика

Онлайн всего: 2
Гостей: 2
Пользователей: 0

Метод прямых вставок с барьером

   Чтобы сократить количество сравнений в алгоритме прямых вставок, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний 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;

Эффективность алгоритма.
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм совершит
Ø N-1 сравнение
Øи 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" будет
Øсравнений (N+1)*N/2,
Øа пересылок (N-1)*(N+3).
Таким образом, этот алгоритм имеет сложность О(N2) по обоим параметрам.



Тэги: прямые вставки, прямые вставки с барьером, алгоритм прямых вставок.

Форма входа
Поиск
Мы в сети
Реклама
Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации
ФОРУМ
У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)
--- Не стесняемся - заходим на форум! ---