Сортировка вставками

 

Идея алгоритма. Будем просматривать массив, начиная с первого элемента по последний. Скажем, что элемент находится на своей месте, если все элементы находящиеся левее его, меньше по значению. И скажем, что элемент не на своем месте, если слева от него есть элементы большие по значению. Тогда если в процессе просмотра массива встретился элемент стоящий не на своем месте, то необходимо определить для него новое место и вставить его туда.

Как это сделать. Вернемся в началу массива и идя от начала найдём элемент, такой что он больше НЕПРАВИЛЬНО СТОЯЩЕГО и в то же время он первый обладающий таким свойством. Назовем его НАЙДЕННЫМ. Тогда место НЕПРАВИЛЬНО СТОЯЩЕГО перед НАЙДЕННЫМ.

Для вставки необходимо выполнить следующие действия: (алгоритм ВСТАВКИ)

§          Запомним значение НЕПРАВИЛЬНО СТОЯЩЕГО

§          Сдвинем массив от НАЙДЕННОГО (включая его) до НЕПРАВИЛЬНО СТОЯЩЕГО (не включая его) на одну позицию.

§          Присвоим значение НЕПРАВИЛЬНО СТОЯЩЕГО элементу перед НАЙДЕННЫМ

 

Алгоритм

 

Для всех элементов массива начиная с первого делать

§                                                Если ТЕКУЩИЙ элемент есть НЕПРАВИЛЬНО СТОЯЩИЙ то

o         Начиная с первого до нахождения первого большего чем НЕПРАВИЛЬНО СТОЯЩИЙ, ищем такой больший. По завершению поиска назовем найденный элемент НАЙДЕННЫМ

o         Выполним ВСТАВКУ

 

Второй вариант

 

Приведенный алгоритм обладает одним существенным недостатком. Для того, чтобы убедится в том, что очередной элемент является НЕПРАВИЛЬНО СТОЯЩИМ необходимо сравнить его со всеми элементами левее его. После этого необходимо определить элемент который мы назвали НАЙДЕННЫМ для чего опять потребуется просмотр всех элементов стоящих левее и сравнение их с НЕПРАВИЛЬНО СТОЯЩИМ. То есть мы выполним одну и ту же работу дважды. Алгоритм записанный ниже свободен от этого недостатка

 

Для всех элементов начиная от первого делать:

§          Назовем очередной элемент ОЧЕРЕДНЫМ

§          ЛЕВЫЙ элемент = Первому

§          Пока ЛЕВЫЙ это не ОЧЕРЕДНОЙ и не была выполнена ВСТАВКА

o                Сравним ЛЕВЫЙ с ОЧЕРЕДНЫМ

o                Если ЛЕВЫЙ больше ОЧЕРЕДНОГО то выполним ВСТАВКУ

o                Если цикл не прервался то ЛЕВЫЙ = СЛЕДУЮЩЕМУ

 

Примечание

 

Видно, что если внутренний цикл будет отработан до конца и ВСТАВКА не выполнена то ОЧЕРЕДНОЙ это очевидно ПРАВИЛЬНО СТОЯЩИЙ, иначе это НЕПРАВИЛЬНО СТОЯЩИЙ.

 

Текст программы

 

MODULE example;

 IMPORT In, StdLog;

PROCEDURE Sort*;

VAR

  a:ARRAY 100 OF INTEGER;

  N,i,k,j,c:INTEGER;

BEGIN

 N:=-1;

 In.Open;

 REPEAT

   N:=N+1;

   In.Int(a[N]);

 UNTIL ~In.Done;

 FOR i:=0 TO N-1 DO

  k:=0;

  WHILE a[i]>a[k] DO k:=k+1;

  END;

  IF k<i THEN

    c:=a[i];

    FOR j:=i TO k+1 BY -1 DO

      a[j]:=a[j-1];

    END;

    a[k]:=c;

  END;

 END;

 FOR i:=0 TO N-1 DO

   StdLog.Int(a[i]);

 END;

END Sort;

END example.