Курсовая работа по дисциплине Компьютерные технологии Тема Упорядочивание элементов массива методом всплытия пузырька Выполнил студент
 Скачать 96.26 Kb.
|
Санкт-Петербургский политехнический университет Петра ВеликогоИнститут энергетикиВысшая школа атомной и тепловой энергетикиКурсовая работапо дисциплине «Компьютерные технологии»Тема «Упорядочивание элементов массива методом «всплытия пузырька»»Выполнил студент гр. 3231301/80001 М.Ю. Чирков Руководитель, старший преподаватель: А. В. Ившин Санкт-Петербург 2019 Санкт-Петербургский политехнический университет Петра Великого Институт энергетики и транспортных систем Кафедра «Атомная и тепловая энергетика» ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ по дисциплине «Компьютерные технологии» студенту Чиркову Михаилу Юрьевичу Тема «Упорядочивание элементов массива методом «всплытия пузырька»» 1. Исходные данные - задается пользователем, в зависимости от выбранной задачи; 2. Содержание пояснительной записки - введение; - математическое и алгоритмическое описание методов решения задачи; - создание приложения (алгоритм работы приложения и обработки событий, результат работы приложения для тестового задания) - исследование и сравнение результатов; - заключение; - приложения (листинг программы)
СодержаниеСанкт-Петербургский политехнический университет Петра Великого 1 Институт энергетики 1 Высшая школа атомной и тепловой энергетики 1 Курсовая работа 1 по дисциплине «Компьютерные технологии» 1 Тема «Упорядочивание элементов массива методом «всплытия пузырька»» 1 Содержание 3 Введение 4 Реализация алгоритма сортировки методом «всплытия пузырька» 5 1.Создание приложения 5 2.Тестирование 5 Заключение 7 Список использованных источников 8 Приложения 9 ВведениеСортировка — это процесс упорядочивания наборов данных одного типа по возрастанию или убыванию значения какого-либо признака. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. В орфографическом словаре будет очень сложно найти нужное слово, если в нём не будет упорядочивание по алфавиту. Существуют следующие методы сортировки элементов: сортировка вставками, сортировка перемещением, сортировка слиянием, сортировка с помощью двоичного дерева, сортировка «пузырька» и другие. Они предполагают последовательное сравнение пары элементов, результатом которого могут быть следующее варианты: первый элемент меньше или равен второму и второй элемент меньше первого. Если алгоритм совершает k сравнений, то всего возможно 2k вариантов комбинаций ответов на них. Количество перестановок из n элементов равняется n!. Используя формулу Стирлинга, получаем оптимальность О(nlog(n)). Для типичного алгоритма хорошее время выполнения — O(nlog(n)), плохое — O(n2), идеальное — O(n). С математической точки зрения, сортировку следует понимать, как процесс перегруппировки заданного множества объектов в некотором определённом порядке. Если существуют элементы a1, …, an, то сортировка есть перестановка этих элементов в массив ak1, …, akn, где при некоторой упорядочивающей функции f выполняются соотношение f(ak1) ≤ f(ak2) ≤ … ≤f(akn). Реализация алгоритма сортировки методом «всплытия пузырька»Создание приложенияАлгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма) [2]. В начале приложения создадим функцию my_bubble_sort(), которая на вход принимает следующие параметры: массив элементов и длину этого массива. В теле функции создаем вложенный цикл, внутри которого сравниваем два соседних элемента массива [1]. Если первый оказывается больше второго, то меняем их местами, иначе рассматриваем следующие элементы. Функция my_print_arr() выводит элементы в читабельном виде. На вход принимает следующие параметры: массив элементов и длину этого массива. В основном теле программы объявляем массив arr со значениями [10.0, 5.6, 7.9, 15.6, 16.9, 11.0, 13.0, 12.0, -1.5, 55.9]. Вычисляем и записываем длину массива в переменную lenght и вызываем функцию my_bubble_sort() с параметрами arr и length. После вызываем функцию my_print_arr() с параметрами arr и length для отображения отсортированного массива. Результатом работы программы для последовательности чисел 10.0, 5.6, 7.9, 15.6, 16.9, 11.0, 13.0, 12.0, -1.5, 55.9 будет -1.50 5.60 7.90 10.00 11.00 12.00 13.00 15.60 16.90 55.90. ТестированиеВ ходе исследования были получены следующие данные: Input: 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 Output: 0.00 0.00 0.00 0.00 0.00 1.00 1.00 1.00 1.00 1.00 Input: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 Output: 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00 10.00 Input: 9, 1, 6, 2, 5, 3, 6, 4, 9, 6, 4, 8, 1, 1 Output: 1.00 1.00 1.00 2.00 3.00 4.00 4.00 5.00 6.00 6.00 6.00 8.00 9.00 9.00 Программа верно выполняет сортировку. ЗаключениеВ курсовой работе я рассмотрел методы решения задач сортировки элементов. Был изучен метод «всплытия пузырька». Результатом работы является реализация данного метода на языке С (см. Приложение 1). Список использованных источниковА.В. Могилев, Л.В. Листрова. Методы программирования. Компьютерные вычисления. СПб.:БХВ-Петербург, 2008. 320с. Дата обращения: 04.12.2019 г. Сортировка пузырьком [Электронный ресурс]. https://ru.wikipedia.org/wiki/Сортировка_пузырьком Загл. с экрана. Яз. Рус. Дата обращения: 04.12.2019 г. ПриложенияПриложение 1 — код программы  |