Методичні рекомендації. Сортування - це процес упорядкування набору даних одного типу по зростанню чи спаданню значення якої-небудь ознаки

Лабораторна робота № 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 елементів випадковими числами. Елементи головної діагоналі відсортувати за незростанням.

Дата добавления: 2015-05-24