Лекция 27.Двумерные массивы. Сортировка двумерного массива.
автор: Садовский Ефим Моисеевич1. Повторение.
Двумерные массивы. Описание. Ввод и вывод. Поиск максимального и минимального элемента массива.
2. Двумерный массив. Сортировка двумерного массива.
Одна из основных задач по обработке двумерных массивов – сортировка (как правило, любые данные в таблице для оптимизации поиска предварительно сортируются, например, телефонный справочник, классный журнал и т.д.).
Существует два основных вида сортировки двумерного массива: сортировка отдельной строки (столбца) и сортировка по конкретной строке (столбцу). Массив до сортировки: Массив после сортировки 2 строки по убыванию:
| 3 | 7 | 5 | 9 | 2 | | 3 | 7 | 5 | 9 | 2 | | 6 | 1 | 8 | 4 | 3 | | 8 | 6 | 4 | 3 | 1 | | 0 | 9 | 5 | 3 | 1 | | 0 | 9 | 5 | 3 | 1 | | 6 | 4 | 2 | 8 | 3 | | 6 | 4 | 2 | 8 | 3 | | 7 | 5 | 9 | 2 | 4 | | 7 | 5 | 9 | 2 | 4 |
Алгоритм такой сортировки сводится к сортировке одномерного массива (действительно, строка или столбец двумерного массива – одномерный массив с фиксированной второй координатой).
Например: Отсортировать вторую строку двумерного массива по убыванию:
program sort;
var a:array[1..10,1..10] of integer;
t,f,n,i,max,k:integer;
begin
{Ввод массива}
write('Введите количество строк массива: ')
readln(n);
write('Введите количество столбцов массива: ')
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('A[',i,',',',j,']=');
readln(a[i,j]);
end;
{Сортировка. Обратите внимание, что в строке m элементов}
for t:=1 to m-1 do
begin
max:=a[2,t];
k:=t;
for i:=t+1 to m do
if a[2,i]>max then
begin
max:=a[2,i];
k:=i;
end;
f:=a[2,t];
a[2,t]:=a[2,k];
a[2,k]:=f;
end;
{Вывод массива на экран }
for i:=1 to n do
begin
for j:=1 to m do
write(A[i,j]:6);
writeln;
end;
end. Программа сортировки готова.
Обратите внимание, что это та же самая сортировка одномерного массива, только при указании индексов для массива во всех случаях фиксируется строка (указывается [2,..]).
Если бы надо было отсортировать столбец, то фиксировался бы второй индекс, например [..,2].
Для сортировки указанной строки, в начале программы номер строки вводился бы в указанную переменную (например, nn), а далее при сортировке вместо конкретного значения (в нашем примере цифра 2) указывалась бы эта переменная (для сортировки строки: [nn,..], для столбца: [..,nn]).
Гораздо чаще встречается сортировка массива по столбцу (строке), в этом случае после сортировки сохраняются данные в строках (столбцах). Например, при сортировке учащихся по среднему баллу переставляются не только средние баллы, но и номера учеников в журнале, чтобы средний балл не записался кому-то другому. Массив до сортировки: Массив после сортировки 2 строки по убыванию:
| 3 | 7 | 5 | 9 | 2 | | 0 | 9 | 5 | 3 | 1 | | 6 | 1 | 8 | 4 | 3 | | 3 | 7 | 5 | 9 | 2 | | 0 | 9 | 5 | 3 | 1 | | 7 | 5 | 9 | 2 | 4 | | 6 | 4 | 2 | 8 | 3 | | 6 | 4 | 2 | 8 | 3 | | 7 | 5 | 9 | 2 | 4 | | 6 | 1 | 8 | 4 | 3 |
Самое главное, что принцип сортировки практически сохраняется, только на каждом шаге не просто определяется максимальный (минимальный) элемент и меняется местами с первым, вторым и т.д., а происходит перестановка соответствующих строк (столбцов), например, строки с максимальным элементом в нужном столбце с первой, затем строки с максимальным элементом из оставшихся со второй и т.д.
Например: Отсортировать двумерный массив по третьему столбцу по убыванию:
program sort;
var a:array[1..10,1..10] of integer;
t,f,n,i,max,k:integer;
begin
{Ввод массива}
write('Введите количество строк массива: ')
readln(n);
write('Введите количество столбцов массива: ')
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('A[',i,',',',j,']=');
readln(a[i,j]);
end;
{Сортировка}
for t:=1 to n-1 do
begin
max:=a[t,3];
k:=t;
for i:=t+1 to n do
if a[i,3]>max then
begin
max:=a[i,3];
k:=i;
end;
{Вместо перестановки элементов, переставляем строки с номерами k и t}
for j:=1 to m do
begin
f:=a[k,j];
a[k,j]:=a[t,j];
a[t,j]:=f;
end;
end;
{Вывод массива на экран }
for i:=1 to n do
begin
for j:=1 to m do
write(A[i,j]:6);
writeln;
end;
end.3. Задачи.
1. Отсортировать третий столбец двумерного массива по возрастанию.
2. Отсортировать двумерный массив по убыванию по пятой строке.
3. Отсортировать двумерный массив по возрастанию k-го столбца.
|
