1. Сортировка с помощью прямого обмена ( метод “пузырька” ).
В этом методе сравниваются два соседних элемента массива.
Если первый из них больше второго, то эти элементы меняют местами (перестановка ) и т.д., т.е. Max элемент выдавливается в конец массива ( при сортировке по возрастанию ). Затем эта операция повторяется снова до окончательного упорядочивания.
i= 1 2 3 4
5 4
1 1
4 1
3 2
1 3
2 3
3 2
4
4
2 5
5
5
Пример 1.
Сортировка одномерного массива (по возрастанию).
Program SORTIROVKA_1;
uses crt;
CONST A:array[1..5] of integer=(5,4,1,3,2);
n=5;
Var I, j, k, m, buf: integer;
BEGIN
for i:=1 to n-1 do { можно to n do}
for j:=1 to n-1 do { можно to n-i do}
if a[j] >a[j+1] then
begin
buf:=a[j+1] ;
a[j+1] :=a[j] ;
a[j] :=buf;
end;
for i:=1 to 5 do
write(a[i],' ');
writeln;
массив A=(5, 4, 1, 3, 2);
i=1 j=1 5>4 да 4, 5, 1, 3, 2
j=2 5>1 да 4, 1, 5, 3, 2
j=3 5>3 да 4, 1, 3, 5, 2
j=4 5>2 да 4, 1, 3, 2, 5 {за один проход выдавили вправо макс=5}
i=2 j=1 4>1 да 1, 4, 3, 2, 5
j=2 4>3 да 1, 3, 4, 2, 5
j=3 4>2 да 1, 3, 2, 4, 5
** j=4 4>5 нет 1, 3, 2, 4, 5 нет смены эл-тов
i=3 j=1 1>3 нет 1, 3, 2, 4, 5
j=2 3>2 да 1, 2, 3, 4, 5
** j=3 3>4 нет 1, 2, 3, 4, 5 больше
** j=4 4>5 нет 1, 2, 3, 4, 5 смен нет
i=4 j=1 нет
j=2 нет это уже лишние j=3 нет прогоны
j=4 нет
Примечание:
В операторе цикла
for j:=1 to n-i do
конечное значение параметра цикла n-i убирает лишние перестановки по j
(сравните со случаем, когда for j:=1 to n-1 do ).
. Модифицированный метод "Пузырька"
Используется для того, чтобы убрать лишние шаги по i .
Этот метод использует цикл REPEAT.
Пока есть хотя бы одна перестановка в сортируемом массиве за один проход цикла по i (т.е. k=1), цикл REPEAT работает, но когда не было ни одной перестановки ( k=0), т.е. все элементы уже выставлены в порядке возрастания / убывания , то происходит выход из цикла REPEAT.
REPEAT
for i:=1 to 4 do
begin
k:=0; { флажок }
for j:=1 to 5-i do
if a[j] >a[j+1] then
begin
k:=1;
buf:=a[j+1]; a[j+1] :=a[j]; a[j] :=buf;
end;
end
UNTIL k=0;
for i:=1 to 5 do
write(a[i],' ');
writeln;
Сортировка методом ВЫБОРА.
массив A=(5, 4, 1, 3, 2);
i
=1
5
4 1 3 2
max=5
2
i
=2
2
4
1 3
5
max=4
3
i
=3
2 3
1
4
5 max=3
1
i
=4
2
1
3
4 5 max=2
1
i=5 1 2 3 4 5
Принцип сортировки методом выбора заключается в следующем:
отыскивается MAX элемент и переносится в конец массива (меняется местами с находящимся там элементом); затем эта операция применяется ко всем элементам, кроме последнего ( так как он уже находится на своем месте) и так далее.
Пример 1 сортировка методом Выбора
В целочисленном массиве Х(5; -7; 16; 12; -5; 22; -8; 15; 6; 2) расставить элементы в возрастающем порядке.
Вывести на экран исходный и отсортированный массивы.
const n=10;
type mass=array[1..n] of integer;