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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 30.08.2011
Размер файла 300,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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


Подобные документы

  • Изучение понятия и основных видов массивов. Ввод массива с клавиатуры и вывод на экран. Сортировка массивов. Метод простых обменов (пузырьковая сортировка). Сортировка простым выбором и простым включением. Решение задач с использованием массивов Паскаля.

    курсовая работа [82,1 K], добавлен 18.03.2013

  • Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритмы сортировки массивов. Анализ проблем реализации и использования различных видов сортировок массивов.

    курсовая работа [640,3 K], добавлен 07.07.2011

  • Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.

    курсовая работа [161,7 K], добавлен 17.12.2015

  • Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.

    реферат [614,8 K], добавлен 12.04.2014

  • Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.

    реферат [189,8 K], добавлен 06.12.2014

  • Широкое использование компьютерных и информационных технологий. Концепции типов данных. Алгоритмы сортировки одномерных массивов. Описание двумерного массива Паскаля. Методы доступа к элементам массивов. Индексные, динамические и гетерогенные массивы.

    курсовая работа [66,3 K], добавлен 07.12.2010

  • Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.

    курсовая работа [291,5 K], добавлен 22.03.2012

  • Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.

    курсовая работа [203,8 K], добавлен 03.12.2010

  • Понятие массива и правила описания массивов в программах на языке С. Рассмотрение основных алгоритмов обработки одномерных массивов. Примеры программ на языке С для всех рассмотренных алгоритмов. Примеры решения задач по обработке одномерных массивов.

    учебное пособие [1,1 M], добавлен 22.02.2011

  • Работа с массивами, их ввод и вывод, организация программ циклической структуры. Способы описания и использования массивов, алгоритмы их сортировки, сортировка выбором и вставками. Алгоритмы поиска элемента в неупорядоченном и упорядоченном массивах.

    лабораторная работа [14,2 K], добавлен 03.10.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.