8.2 Сортировка одномерного массива
Сортировкой называют набор операций, упорядочивающий элементы массива в соответствии с заданным отношением порядка. Например, в упорядоченном массиве A по возрастанию выполняются неравенства вида:
A1 < A2 < … < An-1 < An
Вопрос о возрастании или убывании упорядоченного массива для нас не принципиален. Как правило, программы, сортирующие массив по возрастанию, легко изменяются для сортировки по убыванию.
Существует множество алгоритмов сортировки (пузырьковая сортировка, сортировка по дереву, быстрая сортировка, сортировка слиянием, сортировка Шелла и т. д.), они имеют большую практическую значимость, являются фундаментальными в некоторых областях информатики.
Здесь приводится самый распространенный и очень понятный алгоритм пузырьковой сортировки по возрастанию.
Название «Пузырьковая сортировка» происходит от образной интерпретации, по которой алгоритм заставляет «легкие» элементы мало-помалу всплывать на «поверхность».
Суть алгоритма такова. Начиная с первого, сравниваются два соседних элемента массива A[i] и A[i+l], если A[i] > A[i+1], то элементы меняются местами. В первый раз мы проходим массив начиная с индекса 1, до индекса n - 1, во второй - с 1 до n - 2 и т. д. Любой массив будет отсортирован за n-1 проходов. Таким образом, порядок сложности данного алгоритма (максимальное количество операций проверок и перестановок элементов массива) пропорционален n2/2, хотя массив может быть отсортирован уже после первого прохода.
program p8_2;
const
n = 10; { Константа n задаёт количество элементов в массиве А}
var
a: array [1.. n] of Real;
i, j : integer;
temp : Real;
begin
{ ввод элементов массива }
Writeln (' введите ', n, ' элементов массива: ' ) ;
for i := 1 to n do Read (A [i] ) ; Readln;
{ вывод элементов массива на экран }
Writeln (' Массив до сортировки:' ) ;
for i:= 1 to n do Write(А[i] : 6 : 2, ' ');
Writeln; { Перевод курсора в следующую строку }
{ сортировка }
For j := 1 to n-1 do { цикл перебирает проходы по массиву }
For i : = 1 to n - j do { цикл перебирает пары элементов массива }
if A[i] > A[i + 1] then
begin { ... если A[i] > A[i+1] , то элементы меняются местами }
temp : = A [i+1] ;
A[i+1] := A[i];
A[i] := temp;
end;
{ выводим на экран отсортированный массив }
Writeln (' Массив после сортировки:' ) ;
for i:= 1 to n do Write (A [i] : 6 : 2, ' ') ;
Writeln;
end.
8.3 Массивы с большей размерностью
Возможна следующая организация массива: каждый элемент массива является другой массив. Описание массива в этом случае может выглядеть так:
...: array [... ] of array ...
Подобная запись достаточно громоздка (несколько раз записывается служебное слово array и т. д. ), но синтаксис языка Паскаля позволяет описывать многомерные массивы проще.
<список идентификаторов через запятую> :
Array [ <список диапазонов, через запятую> ] of
<тип элементов>;
Примеры:
1)
М: array[1.. 3] of array [1.. 3] of Real;
Подобное описание эквивалентно следующему:
М: array [1.. 3, 1.. 3] of Real;
В первом случае доступ к элементу осуществляется так:
M[i][j],
а во втором
M[i, j] .
2)
Т: array[1 .. 2, 1 .. 3, 1 .. 4] of Integer;
U: array[1 .. 10, 'A' .. 'Z'] of char;
Работа с n-мерными массивами заставляет программиста организовать n вложенных циклов. Подробнее остановимся на двумерных массивах. Двумерные массивы используются, в основном, для определения матриц (таблиц) с индексами, изменяющимися по строкам и по столбцам (первый индекс – номер строки, второй - номер столбца).
А[1, 1] , А[1, 2] , . . . , A[l, M]
А[2, 1] , А[2, 2] , . . . , А[2, M]
………………………………….
А[N, 1] , A[N,2] , . . . , А[N,M]
Здесь приведён пример двух мерного массива с N строками и M столбцами.
С элементами двумерных массивов можно работать, указывая два индекса (номер строки и номер столбца) через запятую в квадратных скобках.
Примеры:
М[1, 2] := 7;
М[7, 5] := 46;
M[i, j] := 75;
M[k, i] := SQR(M[i, j] + M[j, i] ) ;
Ввод элементов двумерного массива по строкам с клавиатуры:
for i := 1 to n do
for j:= 1 to m do Read (M[i, j]);
или с сообщениями:
for i:= 1 to n do
for j:= l to m do
begin
Write('введите М[', i, ', ' , j, '] ');
Readln(M[i, j]);
end;
Вывод элементов двумерного массива в виде матрицы:
Writeln(' Матрица'); { Заголовок }
for i:=1 to n do
begin
for j:=1 to m do Write(M[i, j] : 7: 3, ' ') ; { Вывод строки}
Writeln; { Переход на следующую строку }
end;
Часто при работе с двумерными массивами (матрицами) приходится оперировать с элементами, обладающими некоторыми признаками, в частности, связанными с положением элементов относительно диагоналей матрицы. Например, элемент находится на главной диагонали рисунок 8.1a, на побочной диагонали рисунок 8.1б, ниже главной диагонали, ниже побочной и т. д. (рисунки 8.1в÷ж).
Положение этих элементов может быть описано следующими математическими соотношениями для матрицы n∙n:
- на главной диагонали - { M[ i , j ] | i = j }
- выше главной диагонали - { M[ i , j ] | i < j }
- выше главной и выше побочной диагонали –
{ M[ i , j ] | i < j } ∩ { M[ i , j ] | i < n-j+1 } и т. д.
a) б) в) г)
д) е) ж)
Рисунок 8.1
Задача. Матрица n*n вводится с клавиатуры, заменить все отрицательные элементы выше главной диагонали их квадратами. Вывести новую матрицу на экран.
program p8_3;
const
n:= 4; { размер матрицы }
var
М: array[1.. n, 1.. n] of integer;
i, j : integer;
begin
{ Ввод элементов матрицы }
for i:= 1 to n do
for j:= 1 to n do
begin
Write('введите М[ ' , i, ', ' , j , '] : ');
Readln(M[i, j ] ) ;
end;
for i: = 1 to n do
for j:= 1 to n do
if i < j then { если элемент выше главной диагонали}
{ и если элемент отрицательный, то заменить его квадратом}
if M[i, j] < 0 then M[i, j] := SQR(M[i, j] ) ;
{ Вывод результатов }
for i:= l to n do
begin
for j:= 1 to n do Write( M[i, j]: 3 , ' ');
Writeln;
end;
end.