Структуры и алгоритмы обработки данных

       

Алгоритм


Алгоритм  сортировки прямым включением таков:

                 for x:=2 to n do

                   x:=a[i]

                   включение х на соответствующее место среди a[1]...a[i]

                 end

В реальном процессе поиска подходящего места удобно, чередуя сравнения

сравнивается с очередным элементом a( j ), а затем либо х вставляется на свободное место, либо a( j ) сдвигается (передается) вправо и процесс "уходит" влево. Обратите внимание, что процесс просеивания может закончиться  при выполнении одного из двух следующих различных условий:

      1. Найден элемент a( j ) с ключом, меньшим, чем ключ у х.

      2. Достигнут левый конец готовой последовательности.

              Procedure StraightInsertion

               Var

                 i,j:index; x:item;

               begin

                 for i:=2 to n do

                   x:=a[i]; a[0]:=x; j:=1;

                   while x<a[j-1] do a[j-1]:=a[j-1]; j:=j-1; end;

                   a[j]:=x

                   end

               end StraightInsertion



Содержание раздела