В работе с информацией наиболее выгодными способами ее хранения являются структуры и массивы. Последние могут содержать любые однотипные данные, которые удобно использовать в работе программы. Они часто применяются в работе интернет-магазинов и в разработке игр. Поэтому данные, содержащиеся в них, многократно сортируются и меняются местами, а над ними выполняются логические или математические операции. Одним из способов наведения порядка в массиве является пузырьковая сортировка. В этой публикации будет изучен ее программный код на языке Си и логика перестановок.
Алгоритм сортировки массива
Технических сложностей для программиста пузырьковая сортировка одномерного массива не представляет, хотя используется достаточно редко из-за своей малой эффективности. Она чаще рассматривается на этапе обучения как самая простая. Однако она далеко не самая эффективная. Ее алгоритм состоит из поочередного сравнения цифр и взаимной перезаписи ячеек, если условие соблюдается.
Пошаговое описание сортировки
На первой итерации постепенно сравнивается два соседних числа. Если левое больше, то оно перезаписывается местами с правым. Минус 8 и 0 условия не удовлетворяют. А потому местами не меняются. Ноль и 5 также не подходят. 5 и 3 — подходят. Однако на такой итерации рамка считывания не попадает на пятерку, а смещается вправо, так как 5 до этого сравнивали с нулем. Это означает, что меняется местами следующая пара — 3 и 9. Далее все замены читателю предлагается просмотреть самостоятельно без авторских комментариев и изучить алгоритм пузырьковой сортировки.
В результате всех итераций массив постепенно сортируется, и происходит это в основном так: большие положительные числа быстро смещаются вправо, тогда как меньшие и отрицательные медленно переставляются влево. Выглядит это, будто пузырьки газа в жидкости быстро всплывают вверх. Из-за такой аналогии алгоритм и был назван пузырьковой сортировкой.
Оценка вычислительной сложности
Идеальный алгоритм сортировки должен быть максимально быстрым. При этом он должен отнимать небольшое количество ресурсов процессора и памяти. И такой процесс, как пузырьковая сортировка массива, не может быть самым энергоэффективным и выгодным. Потому широкого применения он не нашел. Если с памятью на данный момент проблем меньше, то о ресурсах процессора следует беспокоиться. Поскольку цифровые массивы могут быть не просто большими, а громадными, то и расход ресурсов компьютера окажется непредсказуемым.
Если пузырьковая сортировка, в принципе, быстро справляется с наведением порядка в сравнительно небольшом массиве, то в крупном могут быть сбои из-за перерасхода ресурсов. Это значит, что будет нарушаться свойство универсальности, свойственное алгоритму. Причем сортировка пузырьком имеет N-квадрат сложность и очень далека от логарифма N сложности. Вдобавок риск сбоя при обработке крупного массива повышает шансы потери данных в связи с перезаписью ячеек. Гораздо выгоднее в этом плане будет сортировка вставками или алгоритм Шелла.
Программный код
Указанный ниже на графическом приложении компьютерный код для языка Си позволяет осуществить пузырьковую сортировку. Он вынесен в виде отдельной функции типа void. Она не возвращает никаких значений, но использованием указателей меняет местами элементы в зависимости от условий сортировки. В этом случае код решает задачу пузырьковой сортировки массива целых чисел по возрастанию.
Для выполнения этой функции пользователь должен создать массив, который необходимо заполнить нужными значениями. Это можно сделать вручную, задавая размерность и количество элементов на старте программы. Тогда же можно заполнить массив постоянными значениями. Второй вариант — это создание универсальной программы путем декларации крупного одномерного массива на 100 элементов.
Декларирование и инициализация массива
Задав целочисленную переменную и присвоив ей значение, считанное с клавиатуры, можно ограничить количество ячеек, которые будут заполнены. Также можно реализовать функцию ввода элементов массива пользователем с клавиатуры, используя функцию scanf(«%d», &value). В этом примере «%d» - это модифицирующая строка, которая сообщает компилятору, что после сканирования будет получено целочисленное значение. Переменная value будет хранить значение, являющееся размером одномерного целочисленного массива.
Чтобы использовать алгоритм сортировки, следует передать в функцию название массива и его размер. В ситуации, представленной на графическом приложении, вызов функции сортировки будет выглядеть так: BubleSort(dataArray, sizeDataArray). Разумеется, в конце строки после функции следует ставить точку с запятой вместо точки, как этого требуют правила синтаксиса программы. Итак, dataArray – это имя массива, который нужно отсортировать, а sizeDataArray – это его размер.
Передача этих параметров в функцию BubleSort() приведет к тому, что вместо использования sizeArray, как это видно на рисунке, в реальной программе операции будут выполнены с sizeDataArray. Это же означает, что в функции BubleSort() будет использован целочисленный массив dataArray. Аналогичным образом происходит вызов функции printArrayFunction() и ArrayIntegerInputFunction(). Первая ответственна за печать, то есть за вывод в консоль элементов. А вторая нужна для его заполнения элементами, введенными пользователем с клавиатуры.
Такой стиль программирования, когда обособленные операции выносятся в виде функций, значительно повышает читабельность кода и ускоряет его разработку. В подобной программе отдельно вынесено заполнение массива с клавиатуры, его вывод на печать и сама пузырьковая сортировка. Последняя может быть использована для упорядочивания данных или как второстепенная функция, призванная найти минимум и максимум массива.
Сортировка вставками
В сортировке методом вставки предполагается поочередное сравнение каждого элемента и построение цепочки уже отсортированных согласно условию элементов. В итоге результатом каждого последующего сравнения является поиск ячейки, в которую может быть помещено новое значение. Но вставка каждого из них выполняется в уже отсортированную часть массива.
Такая обработка выполняется быстрее и имеет меньшую вычислительную сложность. Код на языке Си представлен на графическом приложении.
Он также вынесен в виде функции, в которую в качестве аргументов передается название нуждающегося в упорядочивании массива и размер массива. Здесь же можно видеть, насколько медленной является пузырьковая сортировка. Вставками аналогичная работа выполняется гораздо быстрее и имеет компактный программный код.
