8.4. Методичні вказівки

Всі основні операції над масивом, які виконуються відповідно варіанту завдання, реалізуються за допомогою функцій У більшості варіантів при ініціалізації масиву використовується генератор випадкових цілих чисел (див. лабораторну роботу №5).

8.5. Зміст звіту

1. Постановка задачі.

2. Варіант завдання.

3. Код програми.

4. Скріншот вікна з результатами роботи програми.

9. Лабораторна робота 8. «Сортування масивів» (4 год.)

Ціль роботи: Одержання навичок сортування даних різними методами. Порівняння ефективності різних методів сортування.

9.1. Теоретичні відомості

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

У даній лабораторній роботі розв'язується задача впорядкування масиву випадкових чисел за допомогою різних методів сортування. Як вихідний масив розглядається одновимірний масив а[i], що складається з N цілочисельних елементів, згенерованих датчиком випадкових чисел. Необхідно розташувати елементи по зростанню (організувати послідовність із неспадних елементів)..

9.1.1. Метод обміну (бульбашковий)

Цей алгоритм залежно від напрямку сортування нагадує «спливання» у процесі обчислень більш «легких» елементів або «занурення» більш «важких» елементів. Розглянемо сортування масиву розміром N, результатом якого повинна бути неспадна послідовність. Процес сортування реалізуємо шляхом «занурення» більш «важких» елементів. При проході масиву від початку до кінця (зліва направо) порівнюються пари сусідніх елементів. Якщо елемент праворуч виявляється менше елемента ліворуч, то вони переставляються. Звичайно кількість проходів не перевищує числа елементів N. Умовою закінчення проходів є відсутність перестановок при черговому проході. Наявність або відсутність перестановки при проході відзначається прапорцем, що приймає відповідно значення 1 або 0.

Запишемо функцію сортування, у списку аргументів якої: *a - покажчик на масив; num - розмір масиву; &mov - посилання на змінну, що враховує число пересилань.

void bubleSort(int *a, int num, int &mov){

int flag = 1; //Встановити прапорець перед початком проходів

for(int i = 1; i <=num; i++){ //Почати прохід масиву

flag = 0; //Черговий прохід

for (int j=0; j < num-1; j++){

if (a[j+1] < a[j]){ //Розміщення ел-тів по зростанню

swap(a[j+1], a[j]);

mov+=3;

flag = 1; //Встановити прапорець при перестановці

display(a, num); //Вивести результат перестановки }

}

if (flag == 0)break; //Якщо не було перестановок

}

}

Приклад сортування масиву методом обміну (білим кольором показані елементи, які не змінюються при ітерації, сірим кольором – елементи, що міняються місцями):

Вихідний масив	22	19	14	23	18
1-я ітерація	19	22	14	23	18
2-я ітерація	19	14	22	23	18
3-я ітерація	19	14	22	18	23
4-я ітерація	14	19	22	18	23
5-я ітерація	14	19	18	22	23
6-я ітерація	14	18	19	22	23