 |
|
Лабораторна робота № 29-30. Масиви. Методи сортування.
Методичні рекомендації
Сортування - це процес упорядкування набору даних одного типу по зростанню чи спаданню значення якої-небудь ознаки. При сортуванні елементи масиву міняються місцями таким чином, що їхні значення виявляються упорядкованими чи по зростанню, чи по спаданню. Якщо в масиві є однакові елементи, то говорять про сортування чи по неспаданню чи по незростанню. У більшості випадків мова йде про сортування одномірного масиву.
Звичайна постановка задачі по сортуванню масиву виглядає в такий спосіб: програма повинна вивести несортований масив цілих чисел на екран, виконати його сортування, а потім вивести відсортований масив.
Розглянемо два методи сортування по незростанню для того самого масиву m з 20 цілих чисел. Для спостереження поточного стану масиву після кожної перестановки елементів будемо виводити його на екран. Для зручності налагодження і тестування масив задається у вигляді типізованої константи.
Лінійне сортування (сортування добором)
Ідея лінійного сортування по незростанню полягає в тім, щоб, послідовно переглядаючи весь масив, відшукати найбільше число і поміняти його місцями з першим елементом. Потім проглядаються елементи масиву, починаючи з другого, знову знаходиться найбільший, котрий міняється місцями з другим і т.д.
const count=20;
m: array [1..count] of byte = (9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i,j,buf,l: byte; a: integer;
begin
writeln('Вихідний массив:');
for i:=l to count do write(' ', m[i]);
writeln; readln;
{зміна розміру невідсортованої частини масиву}
for i:=1 to count-1 do
{порівнюємо почергово i-й елемент невідсортованої частини масиву з усіма від i+1-го до кінця}
for j:=i+l to count do
begin
if m[i]<m[j] then
{ якщо в невідсортованій частині масиву знайшли елемент, більший, ніж і-й, то міняємо їх місцями}
begin
buf:=m[i]; { buf — буфер обміну }
m[i]:=m[j] ;
m[j]:=buf;
end;
for l:=1 to count do write(' ', m[l]); {після сортування}
end;
end.
Сортування методом "бульбашки"
“Бульбашковий” метод сортування – заснований на тому, що в процесі виконання алгоритму більш "легкі" елементи масиву поступово "спливають". Особливістю даного методу є порівняння, а потім, якщо потрібно, і перестановка сусідніх елементів
const count=20;
m: array [1..count] of byte = (9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i,j,buf,l: byte;
begin
writeln('Вихідний массив:');
for i:=l to count do write(' ',m[i]);
writeln;
readln;
for i:=2 to count do
begin
for j:=count downto i do
begin
if m[j-l]<m[j] then { якщо елемент праворуч більше елемента}
{ ліворуч, то "витісняємо" його вліво - бульбашка "спливає"}
begin
buf:=m[j-l]; { перестановка елементів }
m[j-l]:=m[j];
m[j]:=buf;
end;
for l:=1 to count do write(' ',m[l]);
end;
end;
end.
Завдання 1.
Заповнити матрицю розмірності 20х20 елементів випадковими числами. Рядок, номер якого відповідає Вашому варіанту відсортувати одним з методів за неспаданням. Результат вивести на екран.
Завдання 2.
Заповнити матрицю розмірності 20х20 елементів випадковими числами. Елементи головної діагоналі відсортувати за незростанням.