Olgaritmizazziya лабки язык С 4 вариант / лб8 / АіП - Практична робота №8

Практична робота №8

Тема: Створення програм, що обробляють масиви величин різного типу. Одновимірні масиви: Сортування даних.

Мета: навчитися здійснювати впорядкування масивів даних за різними принципами. Отримати практичні навички використання найпростішого алгоритму сортування.

Теоретична частина

Сортування даних - це процес зміни порядку розташування елементів в не впорядкованих структурах даних таким чином, щоб забезпечити зростання або спадання числового значення елемента даних при переході від попереднього елемента до наступному. Тобто для будь-якої пари чисел визначені відносини "більше" або "менше".

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

Існує багато алгоритмів, які забезпечують вирішення задачі сортування. Одні з них володіють низьким швидкодією, інші мають дуже високу ефективність і практично використовуються в сучасних комп'ютерних системах.

При розробці програми можна скористатися різними алгоритмами. Найбільш відомими є наступні:

• лінійний вибір елемента;

• метод мінімального (максимального) елемента;

• метод сортування обміном ("бульбашкове" сортування);

• човникове сортування;

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

Алгоритм лінійного вибору елемента

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

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

Алгоритм методу мінімального (максимального) елемента.

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

Порівняно з алгоритмами вставки і "бульбашки" він у більшості випадків може виявитися більш швидким.

Алгоритм сортування методом «Бульбашки»

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

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

"Бульбашкове" сортування має дуже погані часові характеристики.

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

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

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

Метод сортування вставками полягає в переборі всіх елементів масиву від першого до останнього і вставці кожного чергового елемента на місце серед попередніх йому елементів, упорядкованих раніше таким же способом. Оскільки процес починається з самого першого елемента, то послідовність упорядкованих елементів поступово зростає доти, поки найостанніший елемент не встане на "своє" місце. Звільнення місця для вставки елемента здійснюється шляхом відповідного зсуву групи елементів.

Даний алгоритм також має занадто низьку швидкодію.

Оскільки мета даного курсу – навчання, то в якості алгоритму сортування для розгляду пропонується «Бульбашка».

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

Алгоритм сортування бульбашкою зводиться до повторення проходів по елементам сортованого масиву. Прохід по елементам масиву виконує внутрішній цикл. За кожен прохід порівнюються два сусідніх елементи, і якщо порядок невірний елементи міняються місцями. Зовнішній цикл буде працювати до тих пір, поки маса не буде відсортований. Таким чином зовнішній цикл контролює кількість спрацьовувань внутрішнього циклу Коли при черговому проході за елементами масиву не буде здійснено жодної перестановки, то масив буде вважатися відсортованим. Щоб добре зрозуміти алгоритм, відсортуємо методом бульбашки масив, наприклад, з 7 чисел (див. Таблиця 1).

Вихідний масив: 3 3 7 1 2 5 0

Таблиця 1 — Сортування бульбашкою
№ ітерації	Елементи масиву							Перестановки
вих. масив	3	3	7	1	2	5	0
0	3	3						false
1		3	7					false
2			1	7				7>1, true
3				2	7			7>2, true
4					5	7		7>5, true
5						0	7	7>0, true
пот. масив	3	3	1	2	5	0	7
0	3	3						false
1		1	3					3>1, true
2			2	3				3>2, true
3				0	3			3>0, true
4					3	5		false
5						5	7	false
пот. масив	3	1	2	0	3	5	7
0	1	3						3>1, true
1		2	3					3>2, true
2			0	3				3>0, true
3				3	3			false
4					3	5		false
5						5	7	false
пот. масив	1	2	0	3	3	5	7
	1	2						false
		0	2					2>0, true
			2	3				false
				3	3			false
					3	5		false
						5	7	false
пот. масив	1	0	2	3	3	5	7
	0	1						1>0, true
		1	2					false
			2	3				false
				3	3			false
					3	5		false
						5	7	false
кінцевий масив	0	1	2	3	3	5	7
Кінець сортування

Для того щоб впорядкувати масив вистачило п'яти запусків внутрішнього циклу for. Запустили, цикл for спрацьовував 6 раз, так як елементів в масиві 7, то ітерацій (повторень) циклу for повинно бути на одну менше. На кожній ітерації порівнюються два сусідніх елементи масиву. Якщо поточний елемент масиву більше наступного, то міняємо їх місцями. Таким чином, поки маса не буде відсортований, буде запускатися внутрішній цикл і виконуватися операція порівняння. Зверніть увагу на те, що за кожне повне виконання циклу for як мінімум один елемент масиву знаходить своє місце. В гіршому випадку, знадобиться n-2 запуску внутрішнього циклу, де n - кількість елементів масиву. Це говорить про те, що сортування бульбашкою вкрай не ефективнедля великих масивів.

Приклад написання коду

#include <stdio.h> #include <conio.h> void main() {     int arr[8] = {35, 698, 74, 81, 67, 11, 184, 89},i, flag, tmp;     for (i=0; i<8; i++){        flag = 0;

for (i = 0; i<8; i++)        for (i = 7; i>0; i--){           if (arr[i] < arr[i-1]) {              /* Обмiн значеннями суміжних елементів */              tmp = a[i];

a[i] = a[i-1];

a[i-1] = tmp;              flag++;

/*Інший варіант - swap (a[i], a[i-1]);*/           }        }        /* Якщо масив впорядковано, то обмін не відбувається і        робота циклу припиняється */        if (flag == 0) break;     }     getch(); return 0; }

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

1. Що таке сортування даних? Де і з якою метою можна застосовувати цей процес?

2. Перерахуйте відомі вам алгоритми сортування.

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

4. Охарактеризуйте метод мінімального (максимального) елемента.

5. Охарактеризуйте метод сортування обміном ("бульбашкове" сортування).

6. Охарактеризуйте метод човникового сортування;

7. Охарактеризуйте метод сортування вставками.

8. В чому, на вашу думку, полягають переваги і недоліки методу «Бульбашка»?

Завдання до роботи

1. Відомі значення росту 25 учнів класу, задані в алфавітному порядку прізвищ. Визначити зріст учня, який при шикуванні учнів по росту в порядку зростання займав би 10-е місце по порядку від найвищого учня.

2. Відомі значення максимальної швидкості 15 моделей автомобілів. Визначити максимальну швидкість автомобіля, що є "шостим найшвидшим автомобілем".

3. У кожному з двох класів навчаються по 18 осіб. Відомі середні оцінки кожного учня кожного класу, підраховані по ряду предметів (всі значення для кожного класу різні). Визначити, в якому класі у "третього з найбільш успішних учнів" середня оцінка більше.

4. У кожній з двох фірм працюють по 15 чоловік. Відомі зарплати кожного співробітника кожної фірми. Визначити, в якій фірмі у "п'ятого самого високооплачуваного" співробітника зарплата більше.

5. Відомі значення росту 30 учнів класу, задані в алфавітному порядку прізвищ. Визначити зріст учня, який при шикуванні учнів по росту в порядку спадання займав би 5-е місце по порядку від найнижчого учня.

6. Відомі вартості 12 марок телевізорів (всі значення різні). Визначити вартість телевізора, що є "п'ятим з найдешевших моделей".

7. Відомі маси в кілограмах двадцяти предметів (всі значення різні). Визначити масу предмета, що є "п'ятим з найлегших предметів".

8. У кожному з двох класів навчаються по 23 особи. Відомі значення зростання кожного учня цих класів. Визначити, в якому класі "третій з найвищих учнів" вище.

9. У кожному з двох магазинів продається 10 одних і тих же товарів. Відомі вартості кожного товару в кожному з магазинів (всі вартості в окремих магазинах різні). Визначити, в якому магазині "четвертий з найдорожчих товарів" коштує більше.

10. Відомий зріст 18 осіб. Визначити середнє арифметичне зросту тих двох людей, які б виявилися в середині шеренги в разі побудови її по ранжиру.

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

12. У кожній з двох фірм працюють по 10 чоловік. Відомі зарплати кожного співробітника кожної фірми. Визначити, в якій фірмі у "сьомого самого високооплачуваного" співробітника зарплата менша.