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

1. Що таке блок?

2. Що таке функція на мові С(С++)? Для чого вона застосовується?

3. Опишіть механізм передачі параметрів у функцію.

4. Як використовується оператор return у функції?

5. Що ми маємо на увазі, коли говоримо про тип функції?

6. Чим відрізняються прототип, визначення і виклик функції?

7. Які можливо передати параметри до функції main()?

8. Що таке перевантаження функцій? Для чого воно застосовується?

9. Навести приклади прототипів перевантажених функцій із сигнатурами, що розрізняються за кількістю аргументів і за типом аргументів.

Вивчення методів сортування Мета роботи

Навчитись використовувати методи сортування масивів та навчитись обчислюватись швидкість різних методів сортування.

Навчитися обчислювати швидкість різних методів сортування.

Завдання на лабораторну роботу

1. Ознайомитися з методами сортування масивів.

2. Написати функції до двох методів сортування (за вибором викладача). Використати перевантаження функцій для сортування масивів з елементами типів int, char, float; використати динамічну пам’ять.

3. Сформувати послідовності з

а) 5000 випадкових чисел;

б) 10000 випадкових чисел.

4. Відсортувати одержані послідовності двома обраними викладачем методами.

5. Визначити швидкість обчислення по кожному з методів сортування для різних типів.

6. Одержані результати звести у таблицю (у програмі).

7. Оформити та захистити звіт.

Основні теоретичні відомості

Існує досить багато різних методів сортування, основними з яких є:

а) метод вибору;

б) метод „пузирька”;

в) метод вставок;

г) метод підліку;

д) метод Шелла;

Коротко зупинимось на деяких з них.

Сортування методом вставки (by insection)

Елементи масиву починаючи з другого послідовно додаються у необхідне місце вже упорядкованого масиву, що розташований зліва від поточного елементу a[i]. Позиція включення заздалегідь не відома. Вона визначається порівнянням a[i] з a[i-1], a[i-2] доколи не буде знайдений лівий кінець масиву. Приклад.

const n=10;

int a[n], x, i,j;

…..

for(i=0;i<10;i++){

x=a[i];

j=i;

while(x<a[j-1]){

a[j]=a[j-1]; j--;

}

a[j]=x;

}

…..

res (початок)	4	2	1	8	5
res (i = 1)	2	4	1	8	5
res (i = 2)	1	2	4	8	5
res (i = 3)	1	2	4	8	5
res (i = 4)	1	2	4	5	8

Відсортований масив res = {1, 2, 4, 5, 8}.

Сортування методом простого вибору

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

int a[10],i,j,x,k;

……

for(i=0;i<10;i++){

k=i;

x=a[i];

for(j=i+1; j<10; j++)

if (a[j]<x) {k=j; x=a[k];}

a[k]=a[i];

a[i]=x;}

…..

res (початок)	4	5	2	8	1
res (i = 0)	1	5	2	8	4
res (i = 1)	1	2	5	8	4
res (i = 2)	1	2	4	8	5
res (i = 3)	1	2	4	5	8
res (i = 4)	1	2	4	5	8

Відсортований масив res = {1, 2, 4, 5, 8}.

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

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

…

int a[10],i,j,x,k;

………..

for(i=0;i<10;i++){

for(j=9;j>i;j--){

if(a[j-1]>a[j]){

x=a[j-1];

a[j-1]=a[j];

a[j]=x;

}

}

}

……

res (початок)	4	5	2	8	1
res (i = 0)	1	4	5	2	8
res (i = 1)	1	2	4	5	8
res (i = 2)	1	2	4	5	8
res (i = 3)	1	2	4	5	8
res (i = 4)	1	2	4	5	8