6. Сортування структур даних

Тепер, коли ми вміємо кількома способами впорядковувати послідовність чисел, розглянемо складніші випадки сортування даних. Наприклад, сортування рядків заданої матриці та різні способи

впорядкування записів файла.

6.1. Впорядкування рядків матриці

Задача 26. Дано матрицю А: 10x12. Впорядкувати за зростанням

кожен рядок матриці.

Розв'язок цієї задачі с простим і очевидним узагальненням алгоритму впорядкування одновимірного масиву: з метою впорядкуван­ня кожного рядка, необхідно просто десять разів виконати процедуру сортуваня. Який з описаних раніше методів впорядкування вибрати? Враховуючи оцінки ефективності, наведені у попередньому параграфі, зупинимо свій вибір на сортуванні простими вставками і використаємо оголошену раніше процедуру sortlnsert:

program sortEachLine;

const n=10; m=12 ;

type vector=array[1..rn}of real;

matrix=array[ 1. .n]of vector;

procedure sortlnsert(var a:vector);

{ ВПОРЯДКУВАННЯ МАСИВУ a ПРОСТИМИ ВСТАВКАМИ }

var b:integer; i,j:byte;

begin for j:=2 to m do {шукаємо місце для j-го елемента}

begin b:=a[j]; i:=j-l;

while (i>=l)and(a[i]>b) do {посуваєм впорядковані елементи}

begin a [i+1]:=a[і]; dec(і)

end;{while}

a[i + l] : =b {вставляєм j-й елемент у впорядковану частину}

end;(for j}

end; (sortlnsert)

var a:matrix; i,j:byte;

begin writeln(‘Введіть матрицю A’);

for і:=1 to n do

for j:=l to m do read(a [i,j]);

readln; {закінчили введення матриці А)

{ ВПОРЯДКУВАННЯ РЯДКІВ МАТРИЦІ } for i:=l to n do {перебираємо рядки матриці}

sortlnsert(а [і]) ; {і сортуємо кожен з ник}

{ ВИВЕДЕННЯ МАТРИЦІ }

for i:=1 to n do

begin for j:=l to m do write (a [i,j] ) ;

writeln {закінчили друкувати рядок матриці}

end {for і}

end.

Задача 27. Дано матрицю А:10х12. Впорядкувати рядки матри­ці за зростанням їхніх перших елементів.

Щоб розв'язати цю задачу, необхідно переставити місцями рядки матриці так, щоб їхні перші елементи були впорядковані за зростанням. Тобто кожен рядок розглядають як єдиний запис, елемент структури даних, а його перший елемент - як його ключ. Переміщення рядків матриці є доволі затратною операцією, тому використаємо найеконом-ніший щодо переміщень алгоритм - сортування вибором. Удосконалимо його так, щоб разом з переміщенням ключів відбувалось переставляння рядків.

Введення та виведення матриці у цій задачі нічим не відрізняється від описаного в попередній програмі, тому наведемо тільки той фрагмент програми, який відповідає власне за впорядкування:

type vector=array[1..m]of real;

matrix=array[1..n]of vector; var a:matrix; v:vector; c:real; i,j,k:byte; begin { ... введення матриці } {ВПОРЯДКУВАННЯ}

{ПЕРШОГО СТОВПЦЯ МАТРИЦІ ЗА ДОПОМОГО!) ВИБОРУ НАЙБІЛЬШОГО} {будемо знаходити найбільший елемент невпорядкованої частини} for j:=n downto 2 do {і ставити його на j-e місце}

begin c:=a[l,l]; k: =1; {початкові значення, номер найбільшого} for і:=2 to j do {перевіряємо всі решту}

if a[i,l]>c then begin c:=a[i,l]; k:=i

end; {if & for i}

v:=a[k] ; a [k] :=a[j]; a[j] :=v {міняємо a(j) з найбільшим}

end; {for j}

{ виведення матриці ... }

end.

У цій програмі рядки матриці міняємо місцями за допомогою додаткового массиву V, елементи першого стовпця змінюють місце разом зі своїм рядком.

Задача 28. Дано матрицю А: 10x12. Впорядкувати рядки матри­ці за зростанням сум модулів їхніх елементів.

Ця задача, як і попередня, передбачає впорядкування рядків матриці за зростанням певних ключів, однак, на відміну від попередньої, тут ключі рядків наперед невідомі. їх необхідно обчислити і зберігати під час сортування. Використаємо для зберігання ключів одновимірнии масив Ь. Ного довжина дорівнює кількості рядків матриці:

type vector-array[1..m]of real;

matrix=array[l..n]of vector;

var a:matrix; v:vector;

b:array[1..n]of real;

C:real; i,j,k:byte;

begin { ... введення матриці }

for і:=1 to n do

begin s:=0;

for j:=l to m do s:=s + abs(a [i,j] ) ;

b[i]:=s

end; {for i }

{ ВПОРЯДКУВАННЯ РЯДКІВ МАТРИЦІ }

for j:=n downto 2 do

begin c:=b[l]; k:=l; {початковий ключ}

for і:=2 to j do {перевіряємо решту ключів}

if b[i]>c then begin c:=b[i]; k:=i

end; (if & for i}

b [k] :=b[j] ; b[j] :=c; {МІНЯЄМО КЛЮЧІ}

v:=a[k] ; a [k] :=a[j]; a[j] :=v {i відповідні рядки}

end; (for j }

{ виведення матриці ... }

end .

Впорядкування стовпців матриці виконують схожим методом. Відповідні алгоритми будуть відрізнятися тільки індексами біля елементів матриці та способом виконання перестановок: для стовпців їх потрібно виконувати поелемєнтно. як у п. 4.3, у програмі moveMax.