Сортировка методом пузырька с флагом

Часто оказывается, что после очередной перестановки обмен значениями уже не требуется. Чтобы в этом случае не выполнять повторение просмотров, используют вспомогательную переменную (флаг).

В приведенном выше примере сортировку можно было прекращать уже после 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 &lt; 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;

Обработка строк

Следует также изучить пример «Шифрование шифром Цезаря», рассмотренный ранее.