Алгоритм сортировки включением
Одним из наиболее простых и естественных методов сортировки является сортировка с простыми включениями. Идея алгоритма очень проста.
Пусть имеется массив 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.