Контрольні запитання

1. Якими способами задаються елементи матриць?

2. Як описуються двохмірні масиви?

3. Які операції застосовують до матричних типів?

Лабораторна робота № 11 “Сортування в структурах даних”

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

Питання для вивчення

1. Поняття сортування.

2. Способи сортування:

   1. сортування методом вставки;

   2. сортування методом вибору;

   3. сортування методом обміну.

Теоретичні відомості Поняття сортування

При розв’язанні задачі сортування зазвичай висувається вимога мінімального використання допоміжної пам‘яті, із якої витікає недопустимість застосування допоміжних масивів.

Сортування– це розташування інформації в деякій послідовності за деяким принципом. Сортування даних можна проводити в послідовностях, масивах, файлах.

Для оцінки швидкодії алгоритмів різних методів сортування, як правило, використовують два показника:

• Кількість присвоювань;

• Кількість порівнянь.

Всі методи сортування можна поділити на дві великі групи:

• Прямі методи сортування;

• Покращенні методи сортування.

Прямі методи сортування поділяються на три підгрупи:

• Сортування вставкою

• Сортування вибором

• Сортування обміном ( метод “бульбашок”).

Способи сортування Сортування вставкою

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

Таким чином, алгоритм буде складатися з (n – 1) – го проходу ( n - це розмірність масиву ), кожен з яких буде включати чотири дії:

1. Взяття чергового і – го не відсортованого елемента й збереження її в додатковій змінній;

2. Пошук позиції j у відсортованій частині масиву, в якій присутність взятого елемента не порушить впорядкованості елементів;

3. Зсув елементів масиву від (i – 1) - годо(j – 1) – го праворуч, щоб звільнити знайдену позицію вставки;

4. Вставка взятого елемента в знайдену j – у позицію.

Програма, що реалізує розглянутий алгоритм, буде мати такий вигляд:

Program InsertionSort;

Constn=20;{ довжина масиву }

Type Tvector = array [1. . n] of real;

VarVector : Tvector;

B: real;

i,j, k:integer;

Begin

Writeln(‘ введіть елементи масиву:’);

For i:=1 to n do

Read( Vector[i] );

Readln;

{ - - - - - - - - - - - - }

for i := 2 to n do

begin

B := Vector[i];{взяття не відсортованого елемента}

{цикл пошуку позиції вставки}

j := 1;

while ( B>Vector[j] ) do

j := j+1; {після закінчення циклу індекс jфіксує позицію вставки }

{цикл зсуву елементів для звільнення позиції вставки}

for k := i – 1 downto j do

Vector[ k+1 ] := Vector [k];

{ вставка взятого елемента на знайдену позицію }

Vector [j] := B;

end;

{ - - - - - - - - - - }

writeln (‘відсортований масив:’);

for i :=1 to n do

write ( Vector [i]:8:2 );

writeln;

End.

Сортування вибором

Принцип метода: знаходимо (вибираємо) в масиві елемент з мінімальним значенням на інтервалі від 1-го елемента до n – го (останнього)елемента і міняємо його місцями з першим елементом. На другому кроці знаходимо елемент з мінімальним значенням на інтервалі від 2 – го до n – го елемента і міняємо його місцями з другим елементом. І так далі для всіх елементів до (n – 1) – го.

Програма, що реалізує метод вибору, буде мати наступний вигляд:

Program SebebionSort;

Constn=20; { довжина масиву }

Type Tvector = array [1. . n] of real;

VarVector : Tvector;min: real;

i,Imin,s: integer;

Begin

Writeln(‘ введіть елементи масиву:’);

For i:=1 to n do

Read( Vector[i] );

Readln;

{ - - - - - - - - - - - - }

for s := 1 to n - 1 do

begin

{пошук мінімального елемента в діапазоні}

{від s- го до n- го елемента}

min:=Vector[s];

Imin:=s;

for i := s+ 1 to n do

if Vector[i]<min then

begin

min:=Vector[i];

Imin:=i;

End;

{обмін місцями мінімального і s- го елементів}

Vector[ Imin ] := Vector [s];

Vector [s] := min;

End;

{ - - - - - - - - - - }

writeln (‘відсортований масив:’);

for i :=1 to n do

write ( Vector [i]:8:2 );

writeln;

End.