Создайте свою библиотеку контейнерных классов для матриц на C/C++

Сортировка данных является одной из ключевых задач в программировании. Она используется для упорядочивания информации в различных форматах и структурах данных, что позволяет оптимизировать доступ к данным, выполнять быстрый поиск, эффективно обрабатывать информацию и решать множество прикладных задач. От простейших задач, таких как упорядочивание списка имен, до сложных процессов обработки данных в больших системах, алгоритмы сортировки играют важнейшую роль в разработке программного обеспечения.

В рамках данной работы ставится задача изучения и реализации трех классических алгоритмов сортировки: сортировки вставками, выбором и пузырьком. Кроме того, особое внимание уделяется реализации этих алгоритмов для двух типов массивов — статических и динамических (с использованием структуры данных std::vector из стандартной библиотеки C++).

Цели работы:

1. Провести теоретическое обоснование работы алгоритмов сортировки, описать их принципы, преимущества и недостатки.

2. Реализовать алгоритмы на языке программирования C++ с учетом их применения к статическим и динамическим массивам.

3. Провести экспериментальные замеры времени выполнения каждого алгоритма на массивах из 100 элементов, используя современный инструментарий для работы с временными характеристиками.

Структура работы:

Для достижения поставленных целей работа разделена на две главы:

1. В первой главе рассматриваются теоретические основы алгоритмов сортировки, подробно описываются принципы работы каждого из них, их вычислительная сложность, достоинства и ограничения.

2. Во второй главе приводятся практические реализации алгоритмов на языке C++, а также их применение для сортировки массивов из 100 элементов. Также представлены временные замеры работы каждого алгоритма и их сравнение.

Данная структура позволяет последовательно и комплексно рассмотреть задачу, начиная с теоретических аспектов и заканчивая практическим анализом эффективности алгоритмов.

ВВЕДЕНИЕ 3

ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ СОРТИРОВКИ МАССИВОВ 5

1.1 Сортировка вставками 5

1.2 Сортировка простым выбором 6

1.3 Сортировка простым обменом (пузырьком) 6

ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ 8

2.1 Реализация сортировки вставками 8

2.2 Реализация сортировки выбором 9

2.3 Реализация сортировки пузырьком 10

ЗАКЛЮЧЕНИЕ 13

СПИСОК ЛИТЕРАТУРЫ 15

ПРИЛОЖЕНИЯ 16

Приложение 1. Полный код программы 16

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2020. — 1312 с.

2. Седжвик Р. Алгоритмы на C++: Фундаментальные структуры данных и алгоритмы. — М.: ДМК Пресс, 2015. — 832 с.

3. Никольский С. И. Алгоритмы и структуры данных. — М.: Лаборатория знаний, 2019. — 456 с.

4. Лафоре Р. Объектно-ориентированное программирование на C++. — СПб.: Питер, 2022. — 800 с.

5. Сканциани М., Гудрич М., Тамассия Р. Структуры данных и алгоритмы в C++. — М.: Альпина, 2017. — 624 с.

6. Дейтел Х., Дейтел П. Как программировать на C++. — М.: Вильямс, 2021. — 1088 с.

7. Документация C++: std::vector. [Электронный ресурс]. — URL: https://en.cppreference.com/w/cpp/container/vector

8. Документация C++: std::chrono. [Электронный ресурс]. — URL: https://en.cppreference.com/w/cpp/chrono

9. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Мир, 1983. — 400 с.

10. Шень А. Алгоритмы и программирование. — М.: МЦНМО, 2018. — 256 с.