Лабораторна робота № 5 Сортування елементів масиву

Мета: навчитися застосовувати методи впорядкування одновимірних масивів при розв’язуванні задач.

Теоретичний матеріал

Алгоритм сортування обміном

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

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

Приклад програми.

Program BUBBLESORT;

Uses CRT;

Const N=10; {кількість елементів масиву}

Var A:array[l..N] of integer; {опис масиву}

I,j:integer; {допоміжні змінні}

ADOP:integer; {допоміжна змінна}

Prap:integer;

begin

clrscr;

writeln('Bведіть елементи масиву');

for i:=1 to N do

begin

write('A[',i,']=');

readln(A[i]);

end;

writeln('Macив до сортування:');

writeln;

for i:=1 to N do

write(A[i]:5);

writeln;

I:=2;

repeat

prap:=0;

for j :=N downto 1 do

begin

if A[j]<A[j-l] then

begin

ADOP:=A[j-l];

A[j-1]:=A[j];

A[j]:=ADOP;

PRAP:=1;

end;

end;

i:=i-1;

until PRAP=0;

writeln;

writeln('Macив після сортування:');

writeln;

for i:=l to N do write(A[i]:5);

writeln;

end.

Алгоритм сортування вставками

Масив розділяється на дві частини. Перша частина — упорядкована, друга— ні. З початку в першій частині знаходиться перший елемент масиву, в другій — всі інші.

Береться перший неупорядкований елемент X (перший елемент другої частини масиву) і порівнюється з елементами першої (упорядкованої) частини масиву, починаючи з останнього. Коли знаходиться елемент першої групи Y менший (при упорядкуванні за зростанням) за Х, то всі елементи першої групи, що йдуть після елементу Y, здвигаються на один елемент далі по масиву, а елемент X вставляється після елементу Y на звільнене місце. Перша (упорядкована) частина масиву збільшується на один елемент, а друга, відповідно, зменшується.

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

Алгоритм сортування вибором

Перший елемент масиву приймається за мінімальний і запам’ятовується його номер k (при сортуванні за зростанням). Він порівнюється зі всіма елементами масиву по черзі. Якщо при цьому знаходиться елемент менший за елемент з номером k, то він приймається за мінімальний і k прирівнюється номеру цього елементу. Коли проглянуто весь масив, k дорівнює номеру мінімального елементу в масиві. Мінімальний елемент обмінюється місцями з першим елементом масиву.

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

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

Приклад програми

Program MINSORT;

Uses CRT;

Const N=10; {кількість елементів масиву}

Var A:array[1..n] of integer; {опис масиву}

і,j:integer; {допоміжні змінні}

Amin :integer; {допоміжна змінна для }

{мінімального елементу масиву}

l:integer; {порядковий номер}

{мінімального елементу масиву}

begin

ClrScr;

writeln('Введіть елементи масиву');

for i:=1 to N do

begin

write('A[',i,']=');

readln(A[i]);

end;

writeln('Масив до сортування:');

writeln;

for i:=1 to N do write(A[i]:5);

writeln;

for i:=1 to N do

begin

Amin:=A[i];

l:=i;

while j<=N do

begin

if Amin>A[j]then

begin

Amin:=A[j];

l:=j;

end;

j:=j+1;

end;

А[l]:=А[i];

A[i]:=Amin;

end;

writeln;

writeln('Масив після сортування:');

writeln;

for i:=1 to N do write(A[i]:5);

writeln;

end.