Алгоритм сортировки включением

Одним из наиболее простых и естественных методов сортировки является сортировка с простыми включениями. Идея алгоритма очень проста.

Пусть имеется массив M[0], M[1], ..., M[n-1].. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом [элемент M[i] последовательно сравнивается с элементами M[i-1], M[i-2] ...] и до тех пор, пока для очередного элемента M[j] выполняется соотношение M[j] > M[i], M[i] и M[j] меняются местами. Если удается встретить такой элемент M[j], что M[j] ≤ M[i], или если достигнута нижняя граница массива, производится переход к обработке элемента M[i+1] [пока не будет достигнута верхняя граница массива]. Ниже приведен пример реализации алгоритма сортировки включением:

Общий алгоритм

function Grade (Array[], LengthOfArray) {
     if (LengthOfArray < 2) then return Array[];
     else {
          CurrentIndex:=1;
          while (CurrentIndex < LengthOfArray) do {
               CurrentElement:=Array[CurrentIndex]; i:=0;
               if (CurrentElement < Array[CurrentIndex-i-1]) then Flag=1; else Flag=0;
               while (Flag=1) do {
                    Array[CurrentIndex-i]:= Array[CurrentIndex-i-1];
                    i:=i+1; Flag=0;
                    if (i < CurrentIndex) then {
                         if (CurrentElement < Array[CurrentIndex-i-1]) then Flag=1;
                    }
               }
               Array[CurrentIndex-i]:= CurrentElement;
               CurrentIndex:= CurrentIndex+1;
          }
          return Array[];
     }
}

Pascal

program primer;
const n=5;
var a: array [1..n] of integer;
     i, currentIndex, currentElement: integer;
     flag: boolean;
begin
     // заполнение массива случайными целыми числами от 10 до 99
     randomize;
     for i:=1 to n do begin
          a[i]:=trunc((99-10)*random+10);
     end;

     // вывод исходного массива
     write('Исходный массив: ');
     for i:=1 to n do begin
          write ('a[', i, ']=>', a[i]:3, '; ');
     end;
     writeln;

     // сортировка включением
     if not (n<2) then begin
          currentIndex:=2;
          while (currentIndex<=n) do begin
               currentElement:=a[currentIndex];
               i:=1;
               if (currentElement<a[currentIndex-i]) then flag:=true
               else flag:=false;
               while (flag) do begin
                    a[currentIndex-i+1]:=a[currentIndex-i];
                    inc(i);
                    flag:=false;
                    if (i<currentIndex) then
                         if (currentElement<a[currentIndex-i]) then flag:=true;
               end;
               a[currentIndex-i+1]:=currentElement;
               inc(currentIndex);
          end;
     end;

     // вывод отсортированного массива
     write('Отсортированный массив: ');
     for i:=1 to n do begin
          write ('a[', i, ']=>', a[i]:3, '; ');
     end;
     writeln;writeln;
end.