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

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

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


8.2. метод парных перестановок

 

Самый простой вариант этого метода основан на принципе срав-

нения и обмена пары соседних элементов.

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

 

Пример 8.6. Сортировка одномерного массива методом парных перестановок.

var

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

i,k,n:integer;

q:real;

begin

writeln('Сортировка массива методом парных перестановок');

writeln('Введите количество элементов');

readln(n);

for i:=1 to n do begin

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

readln(a[i]);

end; repeat k:=0;

for i:=1 to n–1 do begin

if a[i]>a[i+1] then begin

q:=a[i]; a[i]:=a[i+1]; a[i+1]:=q; k:=k+1;

end;

end;

until k=0 ;

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

readln;

end.

 

Пример 8.7. Сортировка двумерных массивов. Отсортировать массив по возрастанию элементов методом парных перестановок.

program sortm1;

const n=4;

var

b:array[1..n*n] of integer; a:array[1..n,1..n] of integer; q,i,j,k,g,m,gluk:integer; begin

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

randomize;

for i := 1 to n do begin

for j := 1 to n do

begin    {ввод исходного массива}

gluk:=random(100); {с помощью датчика случайных чисел}

a[i,j]:=gluk–50; write(a[i,j]:4);   {вывод массива}

end;

writeln; end; q:=1;

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

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

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

q:=q+1;

end;

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

k := 0;

for q :=1 to (n*n–1) do begin

if b[q] > b[q+1] then

begin    {меняем элементы местами}

g :=b[q]; b[q]:=b[q+1]; b[q+1] := g;

k :=k +1;

end;

end;

until k =0; {конец сортировки}

q:=1;

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

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

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

q:=q+1; end; writeln('результат'); for i := 1 to n do

begin    {вывод результата}

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

end; readln; end.

 

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

program sortm10;

var

g,n,i,k,q,j:integer;

b:array [1..16] of integer;

a:array [1..4,1..4] of 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;

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

k:=0;

for q:=1 to 14 do

if (q mod 2)=0 then begin

n:=q;    {поиск элемента для сравнения}

repeat n:=n+2

until n<=16;

if b[q]<b[n] then

begin    {перестановка элементов}

g:=b[q]; b[q]:=b[n]; b[n]:=g; k:=k+1;

end;

end;

until k=0;          {конец сортировки}

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.9. Сортировка двумерных массивов. Расположить   по возрастанию элементы каждой строки двумерного массива методом  пар- ных перестановок.

program sortm7;

type

an = array [1..4] of integer;. var

a:array [1..4] of an;

n,l,j:byte;

k, q:integer;

begin

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

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

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

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

begin

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

end;

n:=4;

for j:=1 to 4 do

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

repeat k:=0;

for l:=1 to n–1 do

if a[j,l]>a[j,l+1] then      {перестановка элементов}

begin q:=a[j,l]; a[j,l]:=a[j,l+1]; a[j,l+1]:=q; k:=k+1;

end;

until k=0; {конец сортировки}

end;

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

for j:=1 to 4 do {распечатка результата}

begin

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

writeln; end; readln;

end.

 

Пример           8.10.    Сортировка    двумерных     массивов.       Расположить элементы в столбцах в порядке убывания методом парных перестановок. program sortm6;

type

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

var a:arr; i,k,q,j:integer; begin

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

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

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

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

for i:=1 to 4 do begin

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

end;

for j:=1 to 4 do

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

repeat k:=0;

for i:=1 to 3 do

if a[i,j]<a[i+1,j] then {перестановка элементов}

begin q:=a[i,j]; a[i,j]:=a[i+1,j]; a[i+1,j]:=q; k:=k+1;

end;

until k=0;          {конец сортировки}

end;

writeln('Результат');

for i:=1 to 4 do {распечатка результата}

begin

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

end; readln; end.

 

Задания для самостоятельного выполнения

Нечетные ваpианты задания выполнять модифициpованным методом пpостого выбоpа, а четные – методом паpных пеpестановок.

1–2. Дана последовательность a1,a2,...,a20.   Расположить положительные элементы последовательности, стоящие на нечетных местах, по возрастанию.

3–4.     Дана    последовательность  a1,a2,...,a15.    Расположить  ненулевые элементы последовательности по убыванию.

5–6.  Дана  последовательность x1,x2,...,x20.  Элементы,  cтоящие  на нечетных местах, расположить в порядке возрастания, а на нечетных - в порядке убывания.

7–8. Дана последовательность a1,a2,...,a15. Требуется упорядочить ее по возрастанию абсолютных значений элементов.

9–10.   Дана    последовательность  x1,x2,...,x20.    Требуется       расположить отрицательные элементы последовательности в порядке убывания.

11–12. Дана последовательность a1,a2,...,a20. Расположить положительные элементы последовательности по убыванию.

13–14. Дана последовательность a1,a2,...,a15. Расположить отрицательные элементы по возрастанию.

15–16.  Дана  последовательность a1,a2,...,a15. Расположить элементы  на четных местах по убыванию.

17–18. Дана    последовательность  a1,a2,...,a15.    Расположить  четные элементы последовательности по возрастанию.

19–20. Дана    последовательность  a1,a2,...,a20.    Расположить  нечетные элементы последовательности по убыванию.

21–22. Дана    последовательность  x1,x2,...,x15.    Расположить  четные положительные элементы по возрастанию.

23–24. Дана    последовательность  x1,x2,...,x20.    Расположить  нечетные отрицательные элементы по убыванию.

25–26. Дана    последовательность  x1,x2,...,x20.    Расположить  элементы большие 10 по возрастанию.

27–28. Дана    последовательность  x1,x2,...,x20.    Расположить  элементы меньшие 10 по убыванию.

29–30. Дана последовательность x1,x2,...,x20. Расположить по возрастанию четные элементы последовательности, стоящие на четных местах.

31–32. Расположить элементы в нечетных строках двумерного массива в порядке возрастания значений.

33–34. Расположить элементы в четных столбцах в порядке убывания их значений.

35–36. Расположить  отрицательные          элементы        двумерного    массива          в порядке возрастания значений.

37–38. С помощью процедуры сортировки в каждой строке двумерного массива перенести отрицательные элементы в конец строки.

 

Контрольные вопросы

1. Какова цель сортировки массивов?

2. В чем заключается сортировка модифицированным методом простого выбора?

3. В чем заключается сортировка методом парных перестановок?

4. На каком принципе основан метод парных перестановок?