Сортировка вставками — достаточно простой алгоритм. Как в и любом другом алгоритме сортировки, с увеличением размера сортируемого массива увеличивается и время сортировки. Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения.
Сортируемый массив делится на две части — отсортированная часть и неотсортированная. В начале сортировки первый элемент массива считается отсортированным, все остальные — не отсортированные. Начиная со второго элемента массива и заканчивая последним, программа вставляет неотсортированный элемент массива в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент.
Исходный массив: 5 5 9 3 4 7 2
№
тек элем
1
5
5 false
2
5
5
9 false
3
5
5
9
3 true
4
3
5
5
9
4 true
5
3
4
5
5
9
7 true
6
3
4
5
5
7
9
2 true
7
2
3
4
5
5
7
9
Метод сортировки вставками заключается в переборе всех элементов массива от первого до последнего и вставке каждого очередного элемента на место среди предшествующих ему элементов, упорядоченных ранее таким же способом. Поскольку процесс начинается с самого первого элемента, то последовательность упорядоченных элементов постепенно растет до тех пор, пока самый последний элемент не встанет на "свое" место. Освобождение места для вставки элемента осуществляется путем соответствующего сдвига группы элементов.
Реализация сортировки вставками:
const N = 255;
type TArray = array [1..N] of integer;
procedure InsertSort(var x: TArray);
var
i, j, buf: integer;
begin
for i := 2 to N do
begin
buf := x[i];
j := i - 1;
while (j >= 1) and (x[j] > buf) do
begin
x[j + 1] := x[j];
j := j - 1;
end;
x[j + 1] := buf;
end;
end;
ДЗ.Задание. Составьте программу сортировки одномерного массива рассмотренным методом.
Создать массив целых чисел из N=15 элементов. Заполнить его случайным образом, числами, в диапазоне от 0 до 40. Вывести его на экран. Отсортировать его методом простого обмена ("пузырька”) по убыванию и вывести отсортированный массив на экран.
ДЗ.Задача 2. const m = 15; var arr: array[1..m] of integer; i, j, k: integer; begin randomize; write ('Исходный массив: '); for i := 1 to m do begin arr[i] := random(40); write (arr[i]:4); end; writeln; writeln; for i := 1 to m-1 do for j := 1 to m-i do if arr[j] < arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write ('Отсортированный массив: '); for i := 1 to m do write (arr[i]:4); writeln; readln end.
const m = 15; var s: array[1..m] of integer; n, j, k: integer; begin randomize; write ('Исходный массив: '); for n := 1 to m do begin s[n] := random(40); write (s[n]:4); end; writeln; writeln; for n := 1 to m-1 do for j := 1 to m-n do if s[j] < s[j+1] then begin k := s[j]; s[j] := s[j+1]; s[j+1] := k end; write ('Отсортированный массив: '); for n := 1 to m do write (s[n]:4); writeln; readln end.
ДЗ.Задание. Составьте программу сортировки одномерного массива рассмотренным методом. (по возрастанию) uses crt; type arr=array[1..1000] of integer; var mas: arr; i, j, temp, nom, n: integer; procedure S(mas: arr; n: integer); begin for i:=1 to n-1 do begin nom:=i+1; temp:=mas[nom]; for j:=i+1 downto 2 do begin if (temp<mas[j-1]) then begin mas[j]:=mas[j-1]; nom:=j-1; end; end; mas[nom]:=temp; end; writeln('Отсортированный массив:'); for i:=1 to n do write(mas[i], ' '); end; begin write('Количество элементов в массиве = '); read(n); for i:=1 to n do begin write(i,' элемент = '); read(mas[i]); end; S(mas, n); readkey; end.
uses crt; const a= 15; var arr: array[1..a] of integer; i, j, k: integer; begin clrscr; randomize; write ('Исходный массив: '); for i := 1 to a do begin arr[i] := random(40); write (arr[i]:4); end; writeln; writeln; for i := 1 to a-1 do for j := 1 to a-i do if arr[j] < arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write ('Отсортированный массив: '); for i := 1 to a do write (arr[i]:4); writeln; readln end.
Program sortirovka; var a: array[1..40] of integer; i, j, l: integer; begin writeln ('Введите массив'); for i := 1 to 40 do begin readln (a[i]); end; for i := 1 to 40-1 do for j := 1 to 40-i do if a[j] > a[j+1] then begin l := a[j]; a[j] := a[j+1]; a[j+1] := l end;
Program sortirovka; const n = 15; var arr: array[1..n] of integer; m, j, k: integer; begin randomize; write ('Исходный массив: '); for j := 1 to n do begin arr[j] := random(40); write (arr[j]:5); end; writeln; writeln; for m := 1 to n-1 do for j := 1 to n-j do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write ('Отсортированный массив: '); for j := 1 to n do write (arr[j]:5); writeln; readln end.
Program masiv; const n = 15; var arr: array[1..n] of integer; m, j, k: integer; begin randomize; write ('Исходный массив: '); for j := 1 to n do begin arr[j] := random(40); write (arr[j]:5); end; writeln; writeln; for m := 1 to n-1 do for j := 1 to n-j do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write ('Отсортированный массив : '); for j := 1 to n do write (arr[j]:5); writeln; readln end.
Program masiv; const n = 15; var b: array[1..n] of integer; m, j, k: integer; begin randomize; for j := 1 to n do begin b[j] := random(40); write (b[j]:5); end; writeln; writeln; for m := 1 to n-1 do for j := 1 to n-j do if b[j] > b[j+1] then begin k := b[j]; b[j] := b[j+1]; b[j+1] := k end; for j := 1 to n do write (b[j]:5); writeln; readln end.
