4.2 Сортировка элементов массива

Сортировкой массива называется расстановка элементов массива в возрастающем или убывающем порядке.

Существует множество методов сортировки, рассмотрим два наиболее простых и распространенных метода: метод прямого выбора и метод «пузырька».

Метод прямого выбора (через поиск максимального и минимального элемента).

Алгоритм сортировки по возрастанию (через поиск минимального элемента):

1. Определяется минимальный элемент массива и помещается на 1-е место

2. Среди оставшихся элементов (начиная со 2-го) определяется минимальный элемент и помещается на 2-е место.

3. Среди оставшихся элементов (начиная со 3-го) определяется минимальный элемент и помещается на 3-е место.

4. И т.д. до конца массива.

Пример:

3 5 8 7 1

1|5 8 7 3

1 3|8 7 5

1 3 5 7 8

Программа:

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

i,j: integer;

t: real;

begin

randomize;

for i:= 1 to 10 do

begin

a[i]:=random;

write(a[i]:6:3);

end;

writeln;

for i:= 1 to 9 do

for j:=i+1 to 10 do

if a[i]>a[j] then

begin

t:=a[i];

a[i]:=a[j];

a[j]:=t;

end;

for i:= 1 to 10 do write (a[i]:6:3);

end.

Для обмена значениями двух переменных обычно используют дополнительную переменную (дополнительную ячейку памяти), в приведенной выше программе – это переменная t.

Метод «пузырька» (перестановок).

Алгоритм сортировки по возрастанию:

1. Сравниваются попарно соседние элементы: 1-й со 2-м, 2-й с 3-м, 3-й с 4-м и т.д. до конца массива. Если соседние элементы расположены не по возрастанию, то они меняются местами. Таким образом, максимальный элемент массива «всплывает» на последнее место.

2. Снова сравниваются попарно соседние элементы и меняются местами, если не по возрастанию. Всплывает элемент, меньший максимального, на предпоследнее место.

3. И т.д. до тех пор, пока будут перестановки.

Пример:

3 5 8 7 1

3 5 7 1 8

35 1 7 8

3 1 5 7 8

1 3 5 7 8

Программа:

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

i: integer;

t: real;

b: boolean;

begin

randomize;

for i:= 1 to 10 do

begin

a[i]:=random;

write(a[i]:6:3);

end;

writeln;

repeat

b:=false;

for i:= 1 to 9 do

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

begin

t:=a[i];

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

a[i+1]:=t;

b:=true;

end;

until b=false; {Если b=false – это значит, что не было ни одной перестановки. Следовательно,

массив отсортирован, переходим к выводу отсортированного массива на экран: }

for i:= 1 to 10 do write(a[i]:6:3);

end.

4.3 Многомерные массивы

В качестве элементов массива могут быть значения любого типа, в том числе и массивы, например:

var a: array [N1..N2] of array [N3..N4] of real;

Обычно используют более короткую форму записи:

var a: array [N1..N2, N3..N4] of real; - двумерный массив (матрица), имеет два размера:

N1..N2 – диапазон изменения первого индекса (номер строки)

N3..N4 – диапазон изменения второго индекса (номер столбца)

Пример 1:

var a: array [1..3, 1..4] of integer;

a₁₁ a₁₂ a₁₃ a₁₄

a₂₁ a₂₂ a₂₃ a₂₄

a₃₁ a₃₂ a₃₃ a₃₄

Пример 2:

var b: array [1..5, 1..5, 1..5] of real; - трехмерный массив

Мы будем использовать только одномерные и двумерные массивы.

Обращение к элементам: a[1,3]:=0;

a[3,2]:=5;

В памяти:

	1	2	3	4
1			0
2
3		5

Замечание: Размер любого массива не должен превышать 64 кбайта.

Как вычислить размер массива рассмотрим на примере 1. Массив a имеет размер 3x4, т.е. состоит из 12-ти элементов. Элементы массива a целого типа, т.е. каждый элемент занимает 2 байта памяти. Следовательно, весь массив занимает 24 байта памяти.

При обработке матрицы внешний цикл может быть по номеру строки, а внутренний цикл – по номеру столбца матрицы:

for str:= 1 to 3 do

for stb:= 1 to 4 do

write (a[i,j]);

либо наоборот: внешний цикл - по номеру столбца, а внутренний цикл – по номеру строки матрицы:

for stb:= 1 to 4 do

for str:= 1 to 3 do

write (a[i,j]);

В результате выполнения 1-го фрагмента программы увидим на экране содержимое элементов массива в следующем порядке: a₁₁ a₁₂ a₁₃ a₁₄ a₂₁ a₂₂ a₂₃ a₂₄ a₃₁ a₃₂ a₃₃ a₃₄

В результате выполнения 2-го фрагмента программы - в другом порядке:

a₁₁ a₂₁ a₃₁ a₁₂ a₂₂ a₃₂ a₁₃ a₂₃ a₃₃ a₁₄ a₂₄ a₃₄

Пример 3: Заполнить матрицу размерностью 5х10 целыми случайными числами в диапазоне от 0 до 99 и найти минимальный элемент матрицы и сумму элементов.

var m: array [1..5,1..10] of integer;

i,j,s, min: integer;

begin

randomize;

for i:=1 to 5 do

begin

for j:=1 to 10 do

begin

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

write(m[i,j]:4);

end;

writeln;

end;

s:=0; min:=m[1,1];

for i:=1 to 5 do

for j:=1 to 10 do

begin

s:=s+m[i,j];

if m[i,j]<min then min:=m[i,j];

end;

writeln(‘S = ’,s,’ min = ’,min);

end.

Пример 4: Сформировать матрицу размерностью 5х5, где a_ij=i*j , и вывести ее на экран;

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

var a: array [1..5,1..3] of integer;

sum,i,j: integer;

begin

for i:=1 to 5 do

begin

for j:=1 to 3 do

begin

a[i,j]:=i*j;

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

end;

writeln;

end;

for j:=1 to 3 do

begin

sum:=0;

for i:=1 to 5 do

sum:=sum+ a[i,j];

writeln(‘сумма ’,,j,’-го столбца = ’,sum);

end;

end.

Задачи для самоконтроля

4.1 Какой оператор является ошибочным?

var a: array [0..5] of integer;

p: integer;

Begin

a[1]:=8;

p:=5;

a[p+1]:=7;

4.2 Определите значение sum после выполнения программы:

var a: array [1..2,1..3] of integer;

p, sum: integer;

Begin

a[1,1]:= 8; a[1,2]:= - 6; a[1,3]:= 2;

a[2,1]:= 4; a[2,2]:= 9; a[2,3]:= - 5;

for p:=1 to 2 do

sum:= sum + a[p,p];

end.