Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1339


8.1. модифицированный метод простого выбора

 

В  последовательности  а1,а2,...аn  отыскивается  минимальный элемент, который ставится  на  первое  место. Для  того чтобы  не потерять элемент, стоящий   на   первом   месте, этот   элемент устанавливается  на место минимального. Затем  в   усеченной последовательности (исключая первый элемент) отыскивается минимальный элемент и ставится на второе место и так далее [n–1] раз, пока  не  встанет на свое место предпоследний [n–1] элемент массива А, сдвинув максимальный элемент в самый конец.

 

Пример           8.1.      Сортировка    одномерного  массива          по        возрастанию значений модифицированным методом простого выбора.

 

var

a:array[1..10] of real;

i,j,k,n:integer;

m:real;

begin

writeln('Сортировка массива модифицированным '); writeln('        методом простого выбора'); writeln('Введите количество элементов');       readln(n); for i:=1 to n do

begin

write('Введите A[',i,'] ');

readln(a[i]);

end;

for i:=1 to n–1 do begin

m:=a[i];

k:=i;

for j:=i+1 to n do begin

if a[j]<m then begin m:=a[j];

k:=j; end; end;

a[k]:=a[i]; a[i]:=m; end;

for i:=1 to n do writeln(a[i]:8:4); readln;

end.

 

Пример  8.2. Сортировка двумерных массивов. Переставить элементы по убыванию в двумерном массиве методом модифицированного простого выбора.

 

program sortm2;

var

a:array[1..4,1..4] of integer; b:array[1..16] of integer; n,q,i,j,k,m:integer;

begin    {ввод исходного массива с помощью }

writeln('Исходный массив'); { датчика случайных чисел }

for i:=1 to 4 do begin

for j:=1 to 4 do begin

a[i,j]:=random(30);

write(a[i,j]:3);

end;

writeln;

end;

q:=1;

for i:=1 to 4 do for j:=1 to 4 do

begin    {переписываем двумерный массив в одномерный}

b[q]:=a[i,j];

q:=q+1;

end;

for q:=1 to 15 do          {начало сортировки}

begin m:=b[q];k:=q;

for n:=q+1 to 16 do begin

if b[n]>m then   {поиск максимального элемента}

begin m:=b[n]; k:=n;

end; end; b[k]:=b[q]; b[q]:=m;

end;      {конец сортировки}

q:=1;

for i:=1 to 4 do for j:=1 to 4 do

begin    {переписываем одномерный массив в двумерный}

a[i,j]:=b[q];

q:=q+1; end; writeln('Результат');

for i:=1 to 4 do {вывод результата}

begin

for j:=1 to 4 do write(a[i,j]:3); writeln;

end; readln; end .

 

Пример 8.3. Сортировка двумерных массивов. В двумерном массиве расположить элементы на четных местах по убыванию методом модифицированного простого выбора.

 

program sortm3;

var

a:array[1..4,1..4] of integer; b:array[1..16] of integer; q,n,max,i,j,k:integer;

begin    {ввод исходного массива с помощью} writeln('Исходный массив');         {датчика случайных чисел} randomize;

for i:=1 to 4 do for j:=1 to 4 do

a[i,j]:=random(100);

for i:=1 to 4 do begin

for j:=1 to 4 do write(a[i,j],' ');

writeln;

end;

q:=1;

for i:=1 to 4 do for j:=1 to 4 do

begin    {переписываем двумерный массив в одномерный}

b[q]:=a[i,j];

q:=q+1;

end;

for q:=1 to 7 do {начало сортировки}

begin max:=b[q*2]; k:=q;

for n:=q+1 to 8 do begin

if b[n*2]>max then       {поиск максимального элемента}

begin max:=b[n*2]; k:=n;

end; end; b[k*2]:=b[q*2]; b[q*2]:=max

end;      {конец сортировки}

q:=1;

for i:=1 to 4 do for j:=1 to 4 do

begin    {переписываем одномерный массив в двумерный}

a[i,j]:=b[q];

q:=q+1;

end;

writeln('Полученный массив');

for i:=1 to 4 do {вывод результата}

begin

for j:=1 to 4 do write(a[i,j]:4);

writeln;

end; readln; end.

Пример 8.4. Сортировка двумерных массивов. Расположить элементы в строках двумерного массивa по возрастанию значений модифици- рованным методом простого выбора.

 

program sortm9;

type

arr=array[1..4,1..4] of integer;

var a:arr; i,j,k,f,m:integer; begin

writeln(' Исходный массив');

randomize;        {ввод исходного массива с помощью}

for i:=1 to 4 do {датчика случайных чисел}

for j:=1 to 4 do a[i,j]:=random(100); for i:=1 to 4 do

begin

for j:=1 to 4 do write (a[i,j]:3);

writeln;

end;

for i:=1 to 4 do for j:=1 to 3 do

begin    {начало сортировки по строкам}

m:=a[i,j];

k:=j;

for f:=j+1 to 4 do begin

if a[i,f]<m then {поиск минимального элемента}

begin m:=a[i,f]; k:=f;

end; end; a[i,k]:=a[i,j]; a[i,j]:=m;

end; {конец сортировки} writeln('Полученный массив'); for i:=1 to 4 do

begin    {распечатка результата}

for j:=1 to 4 do write(a[i,j]:3);

writeln;

end;

readln;

end.

 

Пример 8.5. Сортировка двумерных массивов. Расположить по убыванию элементы каждого столбца двумерного массива методом модифицированного выбора.

 

program sortm4;

type

myarr= array[1..4] of integer;

myre = array[1..4] of myarr;

var a:myarr; c:myre; n,k,i,j,q:byte;

begin

writeln('Исходный массив'); {ввод исходного массива с помощью}

randomize;        {датчика случайных чисел}

for i:=1 to 4 do for j:=1 to 4 do c[i,j]:=random(100); for j:=1 to 4 do

begin

for i:=1 to 4 do write(c[i,j],' ');

writeln;

end;

for i:=1 to 4 do

begin    {переписываем каждый столбец двумерного}

q:=1;    {массива в одномерный}

for j:=1 to 4 do begin a[q]:=c[i,j]; q:=q+1;

end;

begin    {начало сортировки}

for q:=1 to 3 do begin

m:=a[q];

k:=q;

for n:=q+1 to 4 do begin

if a[n]>m then {поиск максимального элемента}

begin m:=a[n]; k:=n;

end;

end; a[k]:=a[q]; a[q]:=m; end;

end;      {конец сортировки}

q:=1;

for j:=1 to 4 do begin

c[i,j]:=a[q]; {переписываем каждый одномерный массив}

q:=q+1;            {в столбец двумерного}

end;

end;

writeln('Полученный массив');

for j:=1 to 4 do {вывод результата}

begin

for i:=1 to 4 do write(c[i,j],' ');

writeln; end; readln;

end.