Сформировать массив объемом n элементов, а затем выполнить сортировку методом стандартного обмена
ВВЕДЕНИЕ
В современном мире алгоритмы сортировки данных имеют огромное значение в различных сферах, начиная от науки и заканчивая повседневной жизнью. Существует множество методов сортировки, и каждый из них имеет свои преимущества и недостатки. Одним из самых простых и широко используемых методов является метод стандартного обмена, также известный как пузырьковая сортировка (bubble sort).
Основная идея метода заключается в постепенном перемещении наименьшего элемента массива в его начало. Для этого производится сравнение каждой пары соседних элементов, и, если значение правого элемента меньше значения левого, они меняются местами. Этот процесс продолжается до тех пор, пока все элементы массива не будут отсортированы. В работе также будут описаны основные применения метода стандартного обмена в современном программировании, а также приведены примеры использования данного алгоритма в реальных задачах. Результаты работы могут быть полезны как для начинающих программистов, так и для
СОДЕРЖАНИЕ
Введение………………………………………………………….………………..4
Глава 1. Метод стандартного обмена……………………….….......….………6
1.1. Определение, принцип работы и алгоритм сортировки……....……...….6
1.2. Основные характеристики алгоритма, его преимущества и недостатки….7
1.3. Теорема Big O Notation и расчет сложности алгоритма……...……………8
Глава 2. Реализация сортировки методом стандартного обмена и анализ ее эффективности………………………………...…...….…………………………10
2.1. Формирование массива данных…………………………………...……….10
2.2. Реализация алгоритма сортировки методом стандартного обмена........12
2.3. Измерение времени выполнения сортировки………………………...…14
2.4. Анализ полученных результатов………………………………...………15
Заключение……………………………………………………………………….17
Список литературы………………………………………………………………18
Список литературы
Е. А. Конова, Г. А. Поллак. Алгоритмы и программы. Язык С++: Учебное пособие. — 2-е изд., стер. — СПб.: Издательство «Лань», 2017. — 384 с
Рейзлин В.И. Язык С++ и программирование на нём: учебное пособие / В.И. Рейзлин ; Томский политехнический университет. – 3-е изд., перераб. – Томск : Изд-во Томского политехнического университета, 2021. – 208 с.
Peter Lin. Bubble Sort. A Simple Sorting Algorithm. Medium. 21.08.2019. Доступно по: https://medium.com/@peterlin5301997/bubble-sort-5a66156c942e Дата доступа: 02.05.2023.
Сортировка методом пузырька. Фоксфорд. Доступно по: https://foxford.ru/wiki/informatika/sortirovka-metodom-puzyrka Дата доступа: 02.05.2023.
Dimka Maleev. Алгоритмы сортировки. Bubble Sort. Medium. 05.04.2020. Доступно по: https://medium.com/@dimko1/алгоритмы-сортировки-bubble-sort-a68c5ecbd75d Дата доступа: 02.05.2023
Advantages & Disadvantages of Bubble Sort. Techwalla. Доступно по: https://www.techwalla.com/articles/advantages-disadvantages-of-bubble-sort Дата доступа: 02.05.2023
Описание алгоритмов сортировки и сравнение их производительности. Хабр. 18.09.2017. Доступно по: https://habr.com/ru/articles/335920/ Дата доступа: 02.05.2023
Roman. Что такое «O» большое в программировании? Medium. 13.02.2022 Доступно по: https://medium.com/nuances-of-programming/что-такое-o-большое-в-программировании-e0e436c1a069 Дата доступа: 02.05.2023
Alex. Big O. Хабр. 22.03.2019 Доступно по: https://habr.com/ru/articles/444594/ Дата доступа: 02.05.2023
Fil. Основные концепции библиотеки chrono (C++). Хабр. 29.03.2018. Доступно по: https://habr.com/ru/articles/324984/ Дата доступа: 02.05.2023
<chrono>. Learn.microsoft. 16.11.2022 Доступно по: https://learn.microsoft.com/ru-ru/cpp/standard-library/chrono?view=msvc-160 Дата доступа: 02.05.2023
Структура high_resolution_clock. Learn.microsoft. 03.04.2023. Доступно по: https://learn.microsoft.com/ru-ru/cpp/standard-library/high-resolution-clock-struct?view=msv
В лучшем случае, когда массив уже отсортирован, сложность алгоритма сокращается до O(n), так как в этом случае не происходит никаких перестановок.
Средняя сложность алгоритма сортировки пузырьком также составляет O(n^2), поскольку он требует прохода по массиву n раз и сравнения каждой пары элементов. Эффективность алгоритма существенно уменьшается с увеличением размера входных данных.
Функции, которые используются в Big O Notation:
O(1) не увеличивается с изменением размера входных данных. Таким образом, время обработки O(1) — величина постоянная независимо от того, какие входные данные были переданы. Например: нахождение элемента массива по индексу.
O(log n) - время выполнения алгоритма растет логарифмически с увеличением размера входных данных. Такой тип алгоритмов называется «разделяй и влавствуй»
O(n) - время выполнения алгоритма линейно зависит от размера входных данных.