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

Форум программистов: C++, Basic, Delphi, Pascal, JavaScript
Логин: Пароль:
Запомнить?  
@Mail.ru



Начать новую тему Ответить на тему  [ 1 сообщение ] 
Сортировка массивов Pascal 
Автор Сообщение
Администратор
Аватара пользователя

Регистрация: 03.11.2007
Сообщения: 559
Откуда: Украина
Специальность:

Репутация: 6 [ ? ]
Сообщение Сортировка массивов Pascal
Упорядочить по убыванию методом вставки те элементы каждой строки матрицы, которые расположенные между минимальным и максимальным элементами.

Алгоритм в виде диаграммы действий


Текст программы
program prg5;
{ http://nataliya.kiev.ua }
uses crt;
type TMatrix=array[1..15,1..15]of integer;
procedure InputMatrix(var a:tMatrix;m,n:byte);
var i,j:byte;
q:char;
begin
Writeln('Input by hand?(y/n)');
Readln(q);
Randomize;
for i:=1 to m do
for j:=1 to n do
if (q<>'y')and(q<>'Y')then
a[i,j]:=random(99)
else begin
write('A[',i,',',j,']=');readln(a[i,j]);
end;
end;
procedure OutputMatrix(const a:TMatrix;m,n:byte);
var i,j:byte;
begin
for i:=1 to m do
begin for j:=1 to n do
write(a[i,j]:4);
writeln;end;
end;
procedure MinMax(const a:TMatrix;m,n,i:byte;var j1,j2:byte);
var j:byte;
Min,Max:integer;
begin
j1:=1;j2:=1;
Min:=a[i,1];Max:=a[i,1];
for j:=1 to n do
begin
if a[i,j]<min then begin min:=a[i,j]; j1:=j end;
if a[i,j]>max then begin max:=a[i,j]; j2:=j end;
end;
if j1>j2 then begin
j:=j1; j1:=j2; j2:=j end;
end;
procedure Sort(var a:TMatrix;m,n,l,j1,j2:byte);
var i,j:byte;b:integer;
begin
for i:=j2 downto j1 do
begin
b:=a[l,i];
j:=i;
while (a[l,j+1]>b)and(j<j2)do
begin
a[l,j]:=a[l,j+1];
j:=j+1;
end;
a[l,j]:=b;
end;
end;
procedure Main(var a:tmatrix;m,n:byte);
var i,j,j1,j2:byte;
begin
for i:=1 to m do begin
MinMax(a,m,n,i,j1,j2);
Sort(a,m,n,i,j1,j2); end;
end;
var Matrix:TMatrix;
m,n:byte;
begin
clrscr;
write('m=');readln(m);
write('n=');readln(n);
InputMatrix(Matrix,m,n);
OutPutMatrix(Matrix,m,n);
Main(Matrix,m,n);
writeln('Result:');
OutPutMatrix(Matrix,m,n);
readln;
end.
Результат работы программы
1)
m=6
n=12
Input by hand?(y/n)
n
94 66 26 35 49 98 91 30 89 32 56 73
14 62 27 66 59 59 11 49 78 66 57 73
18 69 2 71 80 28 69 96 40 14 40 12
36 87 97 74 57 18 20 13 14 35 60 19
45 44 57 85 2 69 50 74 26 91 88 84
87 90 83 61 74 28 16 65 38 14 6 94
Result:
94 66 98 49 35 26 91 30 89 32 56 73
14 62 27 66 59 59 78 49 11 66 57 73
18 69 96 80 71 69 28 2 40 14 40 12
36 87 97 74 57 20 18 13 14 35 60 19
45 44 57 85 91 74 69 50 26 2 88 84
87 90 83 61 74 28 16 65 38 14 94 6

2)
m=5
n=5
Input by hand?(y/n)
y
A[1,1]=1
A[1,2]=2
A[1,3]=3
A[1,4]=4
A[1,5]=1
A[2,1]=0
A[2,2]=1
A[2,3]=6
A[2,4]=2
A[2,5]=8
A[3,1]=1
A[3,2]=1
A[3,3]=2
A[3,4]=3
A[3,5]=4
A[4,1]=5
A[4,2]=6
A[4,3]=1
A[4,4]=3
A[4,5]=0
A[5,1]=1
A[5,2]=5
A[5,3]=10
A[5,4]=0
A[5,5]=22
1 2 3 4 1
0 1 6 2 8
1 1 2 3 4
5 6 1 3 0
1 5 10 0 22
Result:
4 3 2 1 1
8 6 2 1 0
4 3 2 1 1
5 6 3 1 0
1 5 10 22 0
Теория к программе
Сортировка массивов
Методы сортировки можно разбить в соответствии с определяющими их принципами на три основные группы:
1. Сортировка с помощью вставки (by Іnsertіon) или с помощью включения
2. Сортировка с помощью выбора (by Selectіon) или с помощью выделения
3. Сортировка с помощью обмена (by Exchange) или пузырьковая.
Каждая группа имеет прямой метод (самый простой) и улучшенный(усложненный) методы сортировки
I. Сортировка с помощью вставки
Принцип сортировки: массив распределяется на отсортированную и неотсортированную части. На первом шаге за отсортированную часть (последовательность) принимается первый элемент массива. Каждый следующий элемент из неотсортированной части вставляем в заранее отсортированную последовательность так, чтобы эта последовательность оставалась отсортированной
При этом надо:
1. Найти место, куда нужно вставить этот элемент
2. Сдвинуть элементы, которые стоят справа в отсортированной части, на одну позицию вправо.
3. На освобожденное место поставить элемент, который анализируется(вставляется).
Два способа выполнения этих действий:
1) каждый следующий элемент сравнивается с элементами в отсортированной части, находится место вставки, все следующие элементы сдвигаются на одну позицию вправо и после этого вставляется элемент;
2) элемент, который вставляется, последовательно, слева направо, сравнивается с любым из элементов в отсортированной части. Если нужно, элемент в отсортированной части сразу сдвигается на одну позицию вправо. Как только найдено нужное место вставки, элемент, который анализируется, вставляется на нужную позицию.
II. Сортировка с помощью прямого выбора
Принцип сортировки: массив также делится на отсортированную и неотсортированную части. На первом шаге весь массив - неотсортированный. В неотсортированной части находится минимальный (или максимальный) элемент и меняется местами с первым элементом неотсортированной части. Граница отсортированной части сдвигается вправо на 1. Процедура выполняется циклически, n-1 раз (последний элемент передвигать не надо ).
III. Сортировка с помощью прямого обмена (пузырьковая)
Принцип сортировки: слева направо поочередно направляется сравнение двух соседних элементов. Если они не упорядочены между собою, то меняются местами. В базовом алгоритме прохождения массива и очередное приведение в порядок повторяются n-1 раз.



11.11.2007 18:53
Профиль ICQ
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 


Кто сейчас на конференции

Зарегистрированные пользователи: Google [Bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
© 2013 «Форум программистов Украины»