Метод сортировки в программировании

Размещено на http://www.allbest.ru/

1. Постановка задачи

сортировка пузырек массив матрица

1.1 Список контуров

· 1,1-1,3-2,4-5,4-4, 3-4,1-1,1

· 3,5-4,6-4,9-7,9-7,6-6,5-3,5

· 7,3-4,6-7,9-7,3

сортировка пузырьковый массив листинг

1.2 Описание метода сортировки

Метод парных перестановок будет работать гораздо эффективнее, если при перестановке пары элементов мы поднимаемся по массиву вверх, найдя место для переставляемого элемента. Это и будет пузырек, который сразу же "всплывет" на соответствующий его весу уровень.

В последовательности AI, А2, ..., AN сравниваются поочерёдно два соседних элемента АК и AK+I, где 1<= К <= N - I; если АК<АК +1, осуществляется перестановка соседних сравниваемых элементов и делается проверка для всех элементов от К-го до 1-го, т.е. движение влево по последовательности с перестановкой соответствующих элементов.

1.3 Условие дополнительного задания

Массив упорядочен.

Если в массиве обнаружится группа, состоящая из трех или более подряд стоящих нулей, то переписать ее в начало массива.

Исходная матрица:

Курсовой проект

2. Разработка проекта

2.1 Обработка массивов

Обработать массивы таким образом, чтобы группы, состоящие из трех или более подряд стоящих нулей, были переписаны в начало массива.

Для обработки в программе написана процедура { procedure obrabotka (str:string;dl:integer;var mas:masr);}, которая включает в себя вложенную процедуру {procedure vivod (mas:masr;dl:byte;str:string);} вывода на монитор результата обработки.

Рис.1

Курсовой проект

Фрагмент исходного текста

procedure obrabotka(str:string;dl:integer;var mas:masr);

var i,l,k,i_end:integer;

begin

k:=0;

for i:=1 to dl do

begin

while mas[i]=0 do

begin

k:=k+1;

if i<dl then

i:=i+1

else break;

end;

if k>=3 then

begin

if i=dl then i_end:=dl

else

i_end:=i-1;

for j:=1 to k do

for l:=i_end downto 1 do

mas[l]:=mas[l-1];

mas[1]:=0;

end;

k:=0;

end;

vivod (mas,dl,str);

end;

Комментарии к выше указанному фрагменту текста

while mas[i]=0 do - цикл с предусловием

begin

k:=k+1;

if i<dl then

i:=i+1

else break;

end;

if k>=3 then

begin

if i=dl then i_end:=dl

else

i_end:=i-1;

for j:=1 to k do

for l:=i_end downto 1 do

mas[l]:=mas[l-1];

mas[1]:=0;

end;

k:=0; стр. 5 из 15

Курсовой проект

2.2 Сортировка полученных массивов методом всплывающего пузырька

Сортировка - это процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака. При сортировки элементы массива меняются местами таким образом, что их значения оказываются упорядоченными или по возрастанию или по убыванию. Если в массиве есть одинаковые элементы, то говорят о сортировке по неубыванию или по невозрастанию.

Один из самых популярных методов сортировки -- «пузырьковый» основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают». Особенностью данного метода является сравнение, а затем, если нужно, и перестановка соседних элементов

Метод нашел свое название в результате следующей аналогии. Если элементы в вертикально расположенном массиве представить себе пузырьками в резервуаре с водой, обладающими весом, равным значению элемента, то каждый просмотр массива и перестановки элемента будут рассматриваться как «всплывание» пузырька на соответствующий его весу уровень

Для сортировки в программе написана процедура {procedure sortirovka (str:string;l:integer;mas:mas;var mas_r.mas); } в которой идет сортировка заданным методом. Процедура включает в себя вложенную процедуру {procedure vivod (str:string;l:integer;mas:mas);} вывода на монитор результата сортировки.

Рис

Фрагмент исходного текста программы

procedure sortirovka (str:string;l:integer;mas:mas;var mas_r:mas);

begin

for i:=2 to L do

for j:=L downto i do

begin

if mas[j-l]>mas[j] then

begin

temp:=mas[j-l];

mas[j-l]:=mas[j];

mas[j]:=temp;

еnd;

end;

vivod (str,L,mas);

for i:=l to 1 do

mas_r[i]:=mas[i];

end;

Комментарии к выше указанному фрагменту текста for i:=2 to L_2 do - цикл обработки значений ячеек массива 2 начиная с ячейки 2 . L2 -- показывает количество ячеек, for j:=L_2 downto i do - цикл обработки значений ячеек массива 2 начиная с последней и заканчивая текущим значением i. if mas_2[j-l]>mas_2[j] - условие которое сравнивает две ячейки - текущую и предыдущую ячеки. И в случае выполнение условия происходит замена их местами begin - начала процесса замены ячеек в зависимости от выбранного направления сортировки temp:=mas_2[j-l] - занесение во вспомогательную переменную значение предыдущей ячейки. mas_2[j-l]:=mas_2[j] -mas_2[j]:=temp; end;

2.3 Вывод на дисплей монитора обновленной матрицы

Матрица должна иметь следующий вид: все контура полученные после сортировки включаются в матрицу по столбцам.



Рис.2

Фрагмент исходного текста

p:=1;

r:=1;

k:=1;

l:=1;

for j:=1 to n do

begin

for i:=1 to m do

begin

{napolnyaem kontur 1}

if

((i>=1) and (i<=4) and (j>=1) and (j<=3))

or

((i>=2) and (i<=5) and (j=4))

then

begin

mas[i,j]:=mas1[p];

p:=p+1;

end

{napolnyaem kontur 3}

else if

((i>=4) and (i<=7))

and

(

{levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

then

begin

mas[i,j]:=mas3[k];

k:=k+1;

if

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

begin

udalit_element(mas2, dl2, r);

end

end

{napolnyaem kontur 2}

else if стр. 9 из 15

((i>=3) and (i<=6) and (j=5)) Курсовой проект

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

begin

mas[i,j]:=mas2[r];

r:=r+1;

end

else

begin

mas[i,j]:=mas4[l];

l:=l+1;

end;

end;

end;

writeln;

writeln('Обновлённый массив:');

otrisovka_matricy(mas, n, m);

readln;

end.

Комментарии к выше указанному фрагменту текста

В рамки соответствующего цветного контура поочерёдно вписываются значения соответствующих ячеек массивов по столбцам.

3. Листинг программного кода задачи

program kurs;

uses crt;

const n=7;

m=9;

dl=75;

color1 = 4;

color2 = 5;

color3 = 10;

color23 = 3;

bgcolor = 15;

type

mas0=array [1..n, 1..m] of integer;

masr=array[1..dl] of integer;

var

i,j,t,k,l,p,r,code,dl1,dl2,dl3,dl4,tmp: integer;

d: text;

mas:mas0;

mas1,mas2,mas3,mas4:masr;

s,w,str:string;

procedure vivod (mas:masr;dl:byte;str:string);

var

i:integer;

begin

writeln(str);

for i:=1 to dl do

write(mas[i]:4);

writeln;

end;

procedure obrabotka(str:string;dl:integer;var mas:masr);

var

i,l,k,i_end:integer;

begin

k:=0;

for i:=1 to dl do

begin

while mas[i]=0 do

begin

k:=k+1;

if i<dl then

i:=i+1

else break;

end;

if k>=3 then

begin

if i=dl then i_end:=dl

else

i_end:=i-1;

for j:=1 to k do

for l:=i_end downto 1 do

mas[l]:=mas[l-1];

mas[1]:=0;

end;

k:=0;

end;

vivod (mas,dl,str);

end;

procedure sortirovka(str:string;dl:integer;var mas:masr);

var

k,i:byte;

temp:integer;

begin

for i:=2 to dl do

for j:=dl downto i do

if mas[j-1]<mas[j] then

begin

temp:=mas[j-1];

mas[j-1]:=mas[j];

mas[j]:=temp;

k:=k+1;

end;

vivod (mas,dl,str);

end;

procedure otrisovka_matricy(var mas:mas0; kol_strok:integer; kol_stolbcov:integer);

var

i,j: integer;

begin

for i:=1 to kol_strok do

begin

for j:=1 to kol_stolbcov do

begin

{risuem kontur 1}

if

((i>=1) and (i<=4) and (j>=1) and (j<=3))

or

((i>=2) and (i<=5) and (j=4))

then

textcolor(color1)

{risuem peresechenie konturov 2 i 3}

else if

(

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

)

and

(

((i>=4) and (i<=7))

and

(

{risuem levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{risuem pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

)

then

textcolor(color23)

{risuem kontur 2}

else if

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

textcolor(color2)

{risuem kontur 3}

else if

((i>=4) and (i<=7))

and

(

{risuem levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{risuem pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

then

textcolor(color3)

{risuem ostalnye elementy}

else

textcolor(bgcolor);

write(mas[i,j]:4);

end;

writeln;

end;

end;

procedure udalit_element(var mas: masr; razmer_matricy: integer; nomer_elementa: integer);

var

i: integer;

begin

for i:=nomer_elementa to razmer_matricy do

begin

mas[i] := mas[i+1];

end;

end;

begin

clrscr;

assign (d, 'matr1.dat');

reset(d);

j:=1;

i:=1;

repeat

readln(d, s);

s:=s+' ';

w:='';

for k:=1 to length(s) do

begin

if s[k]<>' ' then w:=w+s[k] else

begin

val(w,t,code);

w:='';

mas[i,j]:=t;

j:=j+1;

end;

end;

until eof(d);

close(d);

otrisovka_matricy(mas, n, m);

dl1:=0;

dl2:=0;

dl3:=0;

dl4:=0;

for i:=1 to n do

begin

for j:=1 to m do

begin

{napolnyaem kontur 1}

if

((i>=1) and (i<=4) and (j>=1) and (j<=3))

or

((i>=2) and (i<=5) and (j=4))

then

begin

dl1:=dl1+1;

mas1[dl1]:=mas[i,j];

end

{napolnyaem peresechenie konturov 2 i 3}

else if

(

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

)

and

(

((i>=4) and (i<=7))

and

(

{levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

)

then

begin

{napolnyaem matricu 2}

dl2:=dl2+1;

mas2[dl2]:=mas[i,j];

{napolnyaem matricu 3}

dl3:=dl3+1;

mas3[dl3]:=mas[i,j];

end

{napolnyaem kontur 2}

else if

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

begin

dl2:=dl2+1;

mas2[dl2]:=mas[i,j];

end

{napolnyaem kontur 3}

else if

((i>=4) and (i<=7))

and

(

{levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

then

begin

dl3:=dl3+1;

mas3[dl3]:=mas[i,j];

end

else

begin

dl4:=dl4+1;

mas4[dl4]:=mas[i,j];

end;

end;

end;

textcolor(color1);

vivod(mas1,dl1,'¬ Массив 1');

textcolor(color2);

vivod(mas2,dl2,'¬ массив 2');

textcolor(color3);

vivod(mas3,dl3,'¬ массив 3');

textcolor(bgcolor);

vivod(mas4,dl4,'¬ массив 4');

writeln;

readln;

textcolor(color1);

obrabotka('Обработанный массив 1:',dl1,mas1);

textcolor(color2);

obrabotka(''Обработанный массив 2:',dl2,mas2);

textcolor(color3);

obrabotka(''Обработанный массив 3:',dl3,mas3);

textcolor(bgcolor);

obrabotka(''Обработанный массив 4:',dl4,mas4);

writeln;

readln;

textcolor(color1);

sortirovka('Отсортированный массив 1:',dl1,mas1);

textcolor(color2);

sortirovka(''Отсортированный массив 2:',dl2,mas2);

textcolor(color3);

sortirovka(''Отсортированный массив 3:',dl3,mas3);

textcolor(bgcolor);

sortirovka(''Отсортированный массив 4:',dl4,mas4);

writeln;

readln;

p:=1;

r:=1;

k:=1;

l:=1;

for i:=1 to n do

begin

for j:=1 to m do

begin

{napolnyaem kontur 1}

if

((i>=1) and (i<=4) and (j>=1) and (j<=3))

or

((i>=2) and (i<=5) and (j=4))

then

begin

mas[i,j]:=mas1[p];

p:=p+1;

end

{napolnyaem kontur 3}

else if

((i>=4) and (i<=7))

and

(

{levyi treugolnik}

((j>=3) and (j<=6) and (j>=10-i))

or

{pravyi treugolnik}

((j>=6) and (j<=9) and (j<=i+2))

)

then

begin

mas[i,j]:=mas3[k];

k:=k+1;

{peresechenie konturov 2 i 3}

{udalyaem nenuzhnye elementy is kontura 2}

if

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

begin

udalit_element(mas2, dl2, r);

end

end

{napolnyaem kontur 2}

else if

((i>=3) and (i<=6) and (j=5))

or

((i>=4) and (i<=7) and (j>=6) and (j<=9))

then

begin

mas[i,j]:=mas2[r];

r:=r+1;

end

else

begin

mas[i,j]:=mas4[l];

l:=l+1;

end;

end;

end;

writeln;

writeln('Обновлённый массив:');

otrisovka_matricy(mas, n, m);

readln;

end

Размещено на Allbest.ru