Сортировка методом пузырька с флагом
Часто оказывается, что после очередной перестановки обмен значениями уже не требуется. Чтобы в этом случае не выполнять повторение просмотров, используют вспомогательную переменную (флаг).
В приведенном выше примере сортировку можно было прекращать уже после 6-го прохода.
Начальное значение такой переменной-флага равно нулю, а в случае хотя бы одной перестановки ей присваивается ненулевое значение. Сортировка заканчивается, если перестановок не произошло (т.е. значение флага осталось нулевым). В качестве флага можно использовать логическую переменную:
Program ex04_03;
{ ex25_03 сортировка массива методом пузырька }
{ с флагом с выводом после каждого прохода }
const
N = 10; { размер массива }
Var
i, buf, k: integer; { счетчики и буфер обмена }
a: array[1..10] of integer;
flag: integer;
begin
{ ввод массива }
for i:=1 to N do begin
write('a[',i,']= '); readln(a[i]);
end;
{ сортировка }
repeat
flag:=0; { сбросить флаг }
for i:=1 to N-1 do begin
if a[i]>a[i+1] then begin
buf:=a[i]; a[i]:=a[i+1]; a[i+1]:=buf;
flag:=flag+1;
end;
end;
write (flag,': ');
for k:=1 to N do write(a[k]:5);
writeln;
until flag=0;
{ вывод массива }
writeln('отсортированный массив:');
for i:=1 to N-1 do write(a[i]:5);
writeln(a[N]:5);
readln;
end.
Результат работы программы ex25_03 (в начале каждой строки приведено значение переменной flag:
8: 5 1 2 7 6 4 1 3 8 9
6: 1 2 5 6 4 1 3 7 8 9
3: 1 2 5 4 1 3 6 7 8 9
3: 1 2 4 1 3 5 6 7 8 9
2: 1 2 1 3 4 5 6 7 8 9
1: 1 1 2 3 4 5 6 7 8 9
0: 1 1 2 3 4 5 6 7 8 9
отсортированный массив:
1 1 2 3 4 5 6 7 8 9
Алгоритм сортировки выбором
Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наименьший из оставшихся и т.д.
Для этого необходимо выполнить следующую последовательность действий:
1. Определить минимальный элемент массива;
2. Поменять его местами с первым элементом;
3. Определить минимальный элемент среди оставшихся;
4. Поменять его местами со вторым элементом и т.д.;
Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.
Всю операцию по упорядочиванию массива можно разбить на более простые задачи.
Вспомогательная – ввод массива. Пока ввод массива осуществим с клавиатуры:
{ ввод массива }
for k:=1 to N do begin
write('a[',k,']= '); readln(a[k]);
end;
Для контроля введенных значений рекомендуется вывести массив на экран.
Первая задача – поиск минимального элемента. При этом важно запомнить не столько само значение минимального элемента, сколько его номер (индекс):
num:=i;
for j:=i+1 to N do
if a[j]<a[num] then num:=j;
Вторая – поменять местами минимальный элемент с i-ым (очередным):
{ меняем местами a[num] и a[i] }
buf:=a[i]; a[i]:=a[num]; a[num]:=buf;
В приведенном ниже примере для наглядности после каждого обмена на экран также выводится текущее состояние массива.
Program ex04_04;
{ ex25_04 сортировка массива методом выбора }
{ с выводом массива после каждого прохода }
const
N = 10; { размер массива }
Var
a: array[1..N] of integer;
i: integer; { счетчик }
num: integer;{ номер минимального эл-та в части от i до N }
j: integer; { номер эл-та, сравниваемого с минимальным }
buf: integer;{ буфер для обмена значениями }
k: integer; { счетчик для ввода/вывода массива }
begin
{ ввод массива }
for k:=1 to N do begin
write('a[',k,']= '); readln(a[k]);
end;
writeln('исходный массив:');
for k:=1 to N do write(a[k]:5); writeln;
{ сортировка }
writeln('сортировка');
for i:=1 to N-1 do begin
{ ищем минимальный элемент в части от i до N }
num:=i;
for j:=i+1 to N do
if a[j]<a[num] then num:=j;
{ меняем местами a[num] и a[i] }
buf:=a[i]; a[i]:=a[num]; a[num]:=buf;
{ вывод промежуточного состояния массива }
for k:=1 to N do write(a[k]:5); writeln;
end;
writeln('отсортированный массив:');
for k:=1 to N do write(a[k]:5); writeln;
readln;
end.
Результат работы програмы:
исходный массив:
7 5 1 2 9 6 4 1 3 8
сортировка
1 5 7 2 9 6 4 1 3 8
1 1 7 2 9 6 4 5 3 8
1 1 2 7 9 6 4 5 3 8
1 1 2 3 9 6 4 5 7 8
1 1 2 3 4 6 9 5 7 8
1 1 2 3 4 5 9 6 7 8
1 1 2 3 4 5 6 9 7 8
1 1 2 3 4 5 6 7 9 8
1 1 2 3 4 5 6 7 8 9
отсортированный массив:
1 1 2 3 4 5 6 7 8 9
Описанные методы сортировки массивов можно применять как для сортировки массивов по возрастанию, так и для сортировки массивов по убыванию. Для этого просто необходимо определять не минимальный элемент массива, а максимальный. В тексте программы это выражается заменой в некоторых местах знака "<" на знак ">".
Обработка двумерных массивов
Примеры к занятиям
источник: http://wecherkina.ru/
Описание массива в разделе переменных:
const
M = 4; //количество строк
N = 5; //количество столбцов
var
a: array [1..M, 1..N] of integer;
Заполнение массива с клавиатуры и вывод на экран в виде матрицы:
writeln ('Введите M?N чисел: ');
//заполнение массива с клавиатуры
for i := 1 to M do
for j := 1 to N do read (a[i,j]);
//вывод массива на экран
for i := 1 to M do begin
for j := 1 to N do write (a[i,j]:5);
Writeln;
end;
Заполнение массива генератором случайных чисел и вывод на экран в виде матрицы:
randomize;
for i := 1 to M do begin
for j := 1 to N do begin
//заполнение элементов массива случайными числами
a[i,j]:=Random(10);
write (a[i,j]:5); //вывод элемента на экран
end;
writeln;
end;
Подсчёт суммы элементов массива и вывод результата на экран:
S:=0; //обнуляем сумму
//через циклы производим суммирование всех элементов матрицы
for i := 1 to M do
for j := 1 to N do S := S+a[i,j];
writeln('S= ',S); //выводим результат суммы на экран
Подсчёт суммы элементов каждой строки матрицы и вывод результата на экран:
for i := 1 to M do begin
S := 0; //обнуляем сумму
for j := 1 to N do begin
S := S + a[i,j]; //находим сумму элементов строки
end;
writeln('S = ',S); //выводим результат суммы на экран
end;
Подсчёт суммы элементов каждого столбца матрицы и вывод результата на экран:
for j := 1 to N do begin
S := 0; //обнуляем сумму
for i := 1 to M do begin
S := S + a[i,j]; //находим сумму элементов строки
end;
writeln('S = ',S); //выводим результат суммы на экран
end;
Блок заполнения элементов главной диагонали массива (матрицы):
for i:=1 to N do a[i,i] := 1;
или
for i := 1 to N do
for j := 1 to N do if i = j then a[i,j] := 1;
Блок заполнения элементов над главной диагональю массива (матрицы):
for i := 1 to N-1 do
for j := i+1 to N do a[i,j] := 2;
или
for i := 1 to N do
for j := 1 to N do if i < j then a[i,j] := 2;
Блок заполнения элементов под главной диагональю массива (матрицы):
for i := 2 to N do
for j := l to i-1 do a[i,j] := 3;
или
for i := 1 to N do for j := 1 to N do
if i > j then a[i,j] := 3;
Блок заполнения элементов побочной диагонали массива (матрицы):
for i := 1 to N do A[i,N-i+1] := 4;
или
for i := 1 to N do
for j := 1 to N do
if i+j = n+1 then a[i,j] := 4;
Блок заполнения элементов над побочной диагональю массива (матрицы):
for i := 1 to N-1 do
for j := l to N-i do A[i,j] := 5;
или
for i := 1 to N do
for j := 1 to N do
if i+j < n+1 then a[i,j] := 5;
Блок заполнения элементов под побочной диагональю массива (матрицы):
for i := 2 to N do
for j := N downto N-(i-2) do A[i,j] := 6;
или
for i := 1 to N do
for j := 1 to N do
if i+j > n+1 then a[i,j] := 6;
Обработка строк
Следует также изучить пример «Шифрование шифром Цезаря», рассмотренный ранее.