Розробка та дослідження алгоритму сортування шляхом вибору (або внутрішнього обмінного сортування)

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

ФІІТА

Кафедра комп’ютерних наук

Звіт

Про виконання лабараторних робіт

з предмету «Теорія алгоритмів»

Виконав:

Перевірив:

Вінниця 2024

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

Тема: розробка та дослідження алгоритму сортування шляхом вибору

(або внутрішнього обмінного сортування).

Мета: детально проаналізувати та дослідити алгоритм сортування шляхом

вибору (або внутрішнього обмінного сортування).

Хід роботи

Ідея алгоритму сортування шляхом бульбашкового сортування Алгоритм працює таким чином – у масиві порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування за ним нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь .

• Приклад роботи сортування методом бульбашки мовою програмування python:
   [pic 1]

Метод сортування бульбашкою в графічному вигляді :

[pic 2]

Найкращий випадок :В найкращому випадку, коли вхідний масив вже

відсортований, алгоритм виконає одну ітерацію зовнішнього циклу для кожного елемента масиву, порівнявши кожен елемент з наступним і не виконавши жодного обміну. Таким чином, кількість порівнянь буде n-1, де n - кількість елементів у масиві, а кількість обмінів буде рівна 0. Таким чином, у найкращому випадку складність алгоритму буде O(n), де n - кількість елементів у масиві.

Найгірший випадок : В найгіршому випадку, коли вхідний масив відсортований в зворотному порядку, алгоритм буде виконувати n-1 ітерацій зовнішнього циклу, а для кожної ітерації внутрішнього циклу буде виконуватися порівняння та можливий обмін. Таким чином, у найгіршому випадку складність алгоритму буде O(n^2), де n - кількість елементів у масиві.