Лабораторна робота №4

Тема роботи: Ознайомлення із методами сортування, зокрема із методом злиття.

Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. ъ Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу сортування злиттям.

ТЕОРЕТИЧНІ ВІДОМОСТІ

Сортування злиттям – ймовірно, один з найпростіших алгоритмів сортування (серед «швидких» алгоритмів).

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

Приклад. Нехай дано вихідний масив з 7 елементів: 7 4 2 1 0 5 3.

Код даного алгоритму:

void merge(int a[], int size, int l,int x,int r)

{ int temp[size];

for(int i=l;i<=r;++i)

temp[i]=a[i];

int i=l; //поточна позиція для читання із першої послідовності

int j=x+1; //поточна позиція для читання із другої послідовності

int k=l; // поточна позиція для запису в temp

// доки є хоча б один елемент в кожній послідовності

while (i<=x &&j<=r)

{

if (temp[i]<=temp[j])

{

a[k]=temp[i];

++i;

}

else

{

a[k]=temp[j];

++j;

}

++k;

}

//доки перша послідовність непуста

while (i<=x)

{

a[k]=temp[i];

++k;

++i;

}

}

void mergeSort(int a[],int size, int l,int r)//лівий і правий індекс

{

int x;//індекс, за яким ділимо масив

if (l<r)

{

x=(l+r)/2;

mergeSort(a,size,l,x); // сортуємо ліву половину

mergeSort(a,size,x+1,r); // сортуємо праву половину

merge(a,size,l,x,r); //зливаємо результат в загальний масив

}

}

2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ

При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм вибірки.

Використовувати мову програмування C++.

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

3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ

1. Зобразити блок-схему розв’язання завдання;

2. Написати програмну реалізацію виконання завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі;

3. Протестувати на наявність логічних помилок програми;

4. Оформити звіт відповідно до вимог;

5. Захистити виконану роботу.

4.ВИМОГИ ДО ЗВІТУ

Звіт по лабораторній роботі повинен відповідати наступній структурі:

- Титульний лист.

- Словесна постановка задачі.

- Алгоритм розв’язку задачі. В цьому підрозділі описується розробка структури алгоритму, задача розбивається на підзадачі.

- Блок-схема програми.

- Лістинг програми.

- Контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.

- Відповіді на контрольні запитання.

5. КОНТРОЛЬНІ ПИТАННЯ

1. Які ви знаєте методи сортування?
2. Який метод сортування був розглянений на даній лабораторній роботі?
3. Опишіть характеристики даного методу.
4. Порівняєте даний метод із іншими методами сортування вам відомими.
5. Наскільки являється ефективним даний метод сортування?
6. Чи використовують даний метод на практиці, і наскільки часто?