Перелік усіх робіт

Сортування бульбашкою. Сортування вибіркою

Мета роботи

Навчитися реалізовувати алгоритми сортування мовою програмування С++.

Обладнання

Персональний комп’ютер, Visual Studio 2008 або інша середа розробки для мови C++

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

Сортування бульбашкою

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

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

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

Мабуть, найпростіший алгоритм сортування - це сортування вибором. Судячи з назви сортування, необхідно щось вибирати (максимальний або мінімальний елементи масиву). Алгоритм сортування вибором знаходить у вихідному масиві максимальний або мінімальний елементи, в залежності від того як необхідно сортувати масив, по зростанням або за спаданням. Якщо масив повинен бути відсортований по зростанню, то з вихідного масиву необхідно вибирати мінімальні елементи. Якщо ж масив необхідно впорядкувати за спаданням, то вибирати слід максимальні елементи.

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

Сортування вставками

Сортування вставками - досить простий алгоритм. Як в і будь-якому іншому алгоритмі сортування, зі збільшенням розміру сортованого масиву збільшується і час сортування. Основною перевагою алгоритму сортування вставками є можливість сортувати масив у міру його полученія.То є маючи частина масиву, можна починати його сортувати. У паралельному програмуванні така особливість відіграє не останню роль.

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

Хід роботи

Частина 1

1. Завантажити Visual Studio 2008. Знайдіть на робочому столі ярлик з Visual Studio 2008 або Пуск → Всі програми→ Microsoft → Microsoft Visual Studio 2008.

2. Створити новий проект «Visual C++ (консольное приложение Win32)». Файл → Cтворити → Проект, тип проекту «Консольное приложение Win32».

3. Перевірити роботу прикладів, пояснити їх роботу

   Приклади

4. Використовуючи приклад, як зразок, виконати наступні завдання:
   • Написати програму сортування масива методом «бульбашки». Показати час виконання програми в мікросекундах.
   • Написати програму сортування масива методом вибору. Показати час виконання програми в мікросекундах.
   • Написати програму сортування масива методом вставки. Показати час виконання програми в мікросекундах.
5. Виміри часу для всіх алгоритмів (у тому числі з попередньої лабораторної роботи) зробити на 1000, 50000, 200000 елементах. Результати занести в порівняльну таблицю наступного зразка:

	1000	50000	200000
Бульбашка
Вибірка
Вставка масив

1. Додайте програмний код завдання для самомтійного виконання
2. Дайте відповіді на контрольні запитання
3. Збережіть звіт у форматі PDF та надішліть викладачу

Частина 2 (підвищена складність)

1. Використовуючи приклади із Лабораторної роботи 3 модифікуйте програму з першої частини наступним чином:
2. Створіть класс Array, який буде містити три методи для сортування за різними алгоритмами, дві властивості - вхідну та вихідну множину.
3. До класу додайте 3 конструктори:
   • Конструктор без параметру
   • Конструктор з одним параметром для передачі вхідного масиву
   • Конструктор з одним параметром для передачі кількості елементів для створення випадкового масива
4. Кожен метод сортування має повертати час роботи в мікросекундах. Для цього використайте бібліотеку chrono
5. Додайте метод, який буде викликати всі три види сортування та друкувати на екрані у табличному вигляді назву алгоритму, кількість елементів масиву, час сортування.
6. Створіть класс List, який буде містити три методи для сортування за різними алгоритмами, дві властивості - вхідну та вихідну множину. Даний клас має працювати на базі зв’язних списків
7. Додайте до класу List функціонал, аналогічний до класу Array.
8. Створіть підсумкову таблицю наступного вигляду:

	1000	50000	200000
Бульбашка масив
Вибірка масив
Вставка масив
Бульбашка список
Вибірка список
Вставка список

1. Зробіть висновок. Додайте результати у звіт.
2. Збережіть звіт у форматі PDF та надішліть викладачу

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

1. Які основні алгоритми сортування масивів ви знаєте? Які з них є стабільними, а які — нестабільними?
2. Як працює алгоритм сортування “бульбашкою” (Bubble Sort)? Яка його складність у найгіршому, середньому та найкращому випадках?
3. У чому полягає різниця між сортуванням вибором (Selection Sort) та сортуванням вставками (Insertion Sort)? Які їх переваги та недоліки?
4. Що таке стабільність сортування? Наведіть приклади стабільних і нестабільних алгоритмів.
5. Які особливості реалізації сортування для масивів і для зв’язних списків? Чому деякі алгоритми краще підходять для списків?
6. Як працює алгоритм сортування злиттям (Merge Sort) і швидке сортування (Quick Sort)? Які їх часові та просторові складності?
7. Чому сортування вставками часто ефективніше для майже відсортованих даних?
8. Як реалізувати сортування вибором для однозв’язного списку? Які труднощі можуть виникнути?
9. Як впливає структура зв’язного списку (одно- або двозв’язний) на вибір методу сортування?
10. Як можна виміряти і порівняти ефективність різних алгоритмів сортування на практиці?
11. Які типові помилки допускають при реалізації алгоритмів сортування?
12. Як впливає розмір вхідних даних на вибір алгоритму сортування?
13. Які сучасні алгоритми сортування використовуються у стандартних бібліотеках мов програмування?

Довідники та додаткові матеріали

1. Sorting Algorithms (GeeksforGeeks)
2. Bubble Sort — Wikipedia
3. Selection Sort — Wikipedia
4. Insertion Sort — Wikipedia
5. Stable vs Unstable Sorting Algorithms
6. Sorting Algorithms — Visualgo
7. Merge Sort — GeeksforGeeks
8. Quick Sort — GeeksforGeeks