Сортировка массивов

Рассмотрим массив чисел а₁,а₂,а₃,…,а_n. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: а₁ а₂ … а_n. Эта задача называется задачей сортировки массивов или упорядочения массива. Для решения этой задачи можно воспользоваться, например, следующими алгоритмами:

1 Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д. (сортировка выбором).

2 Последовательным просмотром чисел а₁,…,а_n найти наименьшее i такое, что а_i>a_i₊₁. Поменять a_i и а_i+1 местами, возобновить просмотр с элемента а_i+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов (сортировка обменом или методом пузырька).

3 Просматривать последовательно а₂,а₃,…,а_n и каждый новый элемент а_i вставлять на подходящее место в уже упорядоченную совокупность а₁,а₂,а₃,...,а_i-1. Это место определяется последовательным сравнением а_i с упорядоченными элементами а₁,а₂,...,а_i-1 (сортировка вставками).

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

Примеры выполнения задания лабораторной работы

Пример 12. Подсчитать количество положительных элементов в массиве x(10).

Порядок работы:

Шаг 1. Вводим массив x(10).

Шаг 2. Задаем начальное значение количества k = 0.

Шаг 3. Организовываем цикл, который перебирает элементы массива (то есть индекс i), начиная с 1-го и кончая 10-м.

Шаг 4. Если x_i> 0, тогда присваиваем k = k + 1.

Шаг 5. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 3.

Шаг 6. Печатаем k.

Шаг 7. Останов.

Пример 13. Найти минимальный элемент из интервала [5,12] в массиве x(15).

Порядок работы:

Шаг 1. Dводим массив x(15).

Шаг 2. Задаем начальное значение минимального элемента x_min=10²⁰.

Шаг 3. Организовываем цикл, который перебирает элементы массива (то есть индекс i), начиная с 1-го и кончая 15-м.

Шаг 4. Если x_i не принадлежит интервалу [5,12], тогда идем на шаг 6.

Шаг 5. Если x_i< x_min, тогда присваиваем x_min= x_i.

Шаг 6. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 3.

Шаг 7. Печатаем x_min.

Шаг 8. Останов.

Пример 14. Найти максимальный элемент и его номер в массиве x(30) .

Блок-схема

Порядок работы:

Шаг 1. Вводим массив x(30).

Шаг 2. Задаем начальные значения максимального элемента и его номера: x_max= x₁, n_max= 1.

Шаг 3. Организовываем цикл, который перебирает элементы массива (то есть индекс i), начиная с 2-го и кончая 30-м.

Шаг 4. Если x_i>x_max, тогда присваиваем: x_max=x_i, n_max=i.

Шаг 5. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 3.

Шаг 6. Печатаем x_max, n_max.

Шаг 7. Останов.

Пример 15.Найти среднее арифметическое элементов массива Х(20), кратных 3 и принадлежащих интервалу [15,30].

Программа решения данного примера имеет вид:

program pr15;

uses crt;

const N = 20; XN = 15; XK = 30;

type Mas = array[1..N] of integer;

var x:Mas; s,k,i:integer;

SR:REAL; A:BOOLEAN; P:CHAR;

BEGIN CLRSCR;

WRITELN(' ВВЕДИТЕ ',N,' ЧИСЕЛ');

FOR I:=1 TO N DO READ(X[I]);

WRITELN('ИСХОДНЫЙ МАССИВ ');

for i:=1 to N do write(x[i]:4);

writeln; s:=0; k:=0;

for i:=1 to N do

begin

a:=(x[i]<=xk) and (x[i]>=xn);

if (x[i] mod 3 = 0) and a then

begin

s:=s+x[i];

k:=k+1;

end;

IF K>0 THEN SR:=S/K

ELSE SR:=0;

WRITELN('S=',S:5,'K=',K:2,'СРЕДНЕЕ АРИФМ.=’,sr:6:2);

p:=readkey

end.

Пример 16.Найти сумму минимального и максимального отрицательных четных элементов массива Х(15).

Программа решения данного примера имеет вид:

program pr16;

uses crt;

const N = 15;

type Ind = 1..N;

Mas = array[Ind] of integer;

var x:Mas; max,min,s,i:integer;

a:boolean; p:char;

BEGIN CLRSCR;

WRITELN(' ВВЕДИТЕ ',N,' ЧИСЕЛ');

FOR I:=1 TO N DO READ(X[I]);

WRITE(' ':20, 'ИСХОДНЫЙ МАССИВ');

for i:=1 to N do

write(x[i]:4); writeln;

max := -maxint;

min := maxint;

for i:=1 to N do begin

a := (x[i]<=0) and (x[i] mod 2 = 0);

if (x[i]>max) and a then max := x[i];

if (x[i]<min) and a then min := x[i];

end;

S := MAX + MIN;

WRITELN(' ':10,'MAX=',MAX:4,'MIN = ',MIN:4);

WRITELN(' ':20, 'СУММА = ',S:4);

p:=readkey

end.

Пример 17. Сформировать новый массив из положительных элементов исходного массива x(15).

Порядок работы:

Шаг 1. Вводим массив x(15).

Шаг 2. Устанавливаем исходный индекс рабочего массива j=0.

Шаг 3. Организовываем цикл, который перебирает элементы исходного массива (то есть индекс i), начиная с 1-го и кончая 15-м.

Шаг 4. Если x_i£ 0, то идем на шаг 7.

Шаг 5. Устанавливаем индекс следующего элемента рабочего массива j = j + 1.

Шаг 6. Присваиваем элемента рабочего массива значения элемента исходного массива y_j= x_i.

Шаг 7. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 3.

Шаг 8. Печатаем j элементов рабочего массива y.

Шаг 9. Останов.

Пример 18.Сформировать и вывести на печать два массива, которые содержат значения и индексы отрицательных элементов исходного массива В(15).

Программа решения данного примера имеет вид:

program pr18;

uses Crt;

const N=15;

type Mas1=array[1..N] of real;

Mas2=array[1..N] of integer;

VAR B,X:MAS1; Y:MAS2; I,J:INTEGER; P:CHAR;

BEGIN CLRSCR;

WRITELN(' ВВЕДИТЕ ',N,' ЧИСЕЛ');

FOR I:=1 TO N DO READ(B[I]);

WRITELN(' ':20, 'ИСХОДНЫЙ МАССИВ');

for i:=1 to N do write(b[i]:5:1);

writeln;

j:=0;

for i:=1 to N do begin

if b[i]<0 then

begin

j:=j+1;x[j]:=b[i];y[j]:=i;

end;

END;

WRITELN(' ':10, 'НОВЫЕ МАССИВЫ');

IF J>0 THEN FOR I:=1 TO J DO

WRITELN(' ':5,'X(',I,')=',X[I]:5:1, 'Y(',I,')=',Y[I]:2)

ELSE WRITELN(' ТАКИХ ЭЛЕМЕНТОВ НЕТ);

p:=readkey

end.

Пример 19. Найти сумму двух наибольших отрицательных элементов массива x(15).

Порядок работы:

Шаг 1. Dводим массив x(15).

Шаг 2. Устанавливаем исходный индекс рабочего массива j=0.

Шаг 4. Если x_i³ 0, то идем на шаг 7.

Шаг 5. Устанавливаем индекс следующего элемента рабочего массива j = j + 1.

Шаг 6. Присваиваем элемента рабочего массива значения элемента исходного массива y_j= x_i.

Шаг 7. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 3.

Шаг 8. Если j < 2, то выдаем сообщения «Массив не сформирован» и идем на шаг 17.

Шаг 9. Организовываем цикл, который определяет количество просмотров рабочего массива (то есть индекс k), начиная с 1-го и кончая j-м.

Шаг 10. Организовываем цикл, определяющий просматриваемую пару чисел рабочего массива (т.е. индекс i), начиная с 1-го и кончая (j-1)-м.

Шаг 11. Если первый элемент не больше второго, то идем на шаг 13.

Шаг 12. Меняем два элемента местами:

c = y_i; y_i= y_i+1; y_i+1= c.

Шаг 13. Если цикл по i не закончился, идем на начало цикла, то есть на шаг 10.

Шаг 14. Если цикл по k не закончился, идем на начало цикла, то есть на шаг 9.

Шаг 15. Вычисляем сумму s = y_j+ y_j-1.

Шаг 16. Печатаем s.

Шаг 17. Останов.

Пример 20.Найти произведение четырех наименьших положительных кратных 5 чисел исходного массива Х(20).

Сначала формируем новый массив из положительных кратных 5 элементов исходного массива, а затем полученный массив сортируем методом выталкивания (пузырька). Программа имеет вид:

program pr20;

uses crt;

LABEL 1;

const n=20;

type raz=1..N; mac=array [raz] of integer;

VAR X,A:MAC; D,I,J,K,R:INTEGER; P:CHAR;

BEGIN CLRSCR; WRITELN('ВВЕДИ ',N,' ЧИСЕЛ');

FOR I:=1 TO N DO READ(X[I]);

WRITELN(' ':20,'ИСХОДНЫЙ МАССИВ');

FOR I:=1 TO N DO WRITE(X[I]:4);

{ ФОРМИРОВАНИЕ НОВОГО МАССИВА }

writeln; j:=0;

for i:= 1 to N do begin

IF (X[I]>0) AND (X[I] MOD 5 = 0) THEN

BEGIN J:=J+1; A[J]:=X[I]; END; END;

IF J=0 THEN WRITELN(' МАССИВ НЕ СФОРМИРОВАН'): GOTO 1;

{ СОРТИРОВКА ПО ВОЗРАСТАНИЮ }

for k:= 1 to j do

for i:= 1 to j-k do

if a[i+1]<a[i] then

BEGIN D:=A[I]; A[I]:=A[I+1]; A[I+1]:=D; END;

WRITELN(' ':5,'ОТСОРТИРОВАННЫЙ МАССИВ');

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

if j>=4 then begin r:=1;

for i:=1 to 4 do r:=r*a[i];

WRITELN('ПРОИЗВЕДЕНИЕ 4- Х НАИМЕНЬШИХ=',R:6);END

ELSE WRITELN('МАССИВ НЕ СОДЕРЖИТ 4 ПОЛОЖИТЕЛЬНЫХ КРАТНЫХ 5 ЭЛЕМЕНТОВ');

1: p:=readkey

end.