Сортировка пузырьком: описание и реализация

Информационные массивы иногда требуют определенных действий для оптимизации данных. Примером может послужить сортировка. Существуют различные методы реализации соответствующей операции. Самый простой – при помощи «пузырькового» алгоритма.

Далее предстоит познакомиться с этой концепцией более подробно. Необходимо выяснить особенности и принципы реализации «пузырькового» метода сортировки. Также предстоит познакомиться с кодом, благодаря которому получится реализовать соответствующий алгоритм.

Определение

Сортировка пузырьком – это универсальная сортировка. Она предусматривает обработку массивов с переменными (int) и базируется на сравнении позиций элементов. Работает намного медленнее некоторых других подходов к сортировке, зато является одним из самых простых в плане реализации.

«Пузырьковый» метод предусматривает следующие особенности:

• эта концепция служит базой для более сложных алгоритмов сортировки (примером может послужить «перемешивание»);
• в сравнении с другими алгоритмами работает медленно (особенно если предстоит работать с крупными информационными массивами);
• рекомендуется для применения к небольшим массивам;
• встречается в различных языках программирования;
• имеет сложность O(n²);
• легко осваивается программистами.

The bubble sort C называется не только «пузырьковым методом», но и «сортировкой простыми обменами».

Алгоритм работы

The bubble sort – алгоритм с простой реализацией. Он базируется на сравнении соседних элементов массива. Простой условный пример поможет лучше понять принципы функционирования алгоритма.

Пусть изначально будет дан массив с int i. Его необходимо отсортировать при помощи the bubble sort. Операция выполняется в несколько шагов:

1. Сначала система проходит по всему массиву и просматривает его составляющие.
2. Каждый элемент массива сравнивается с соседним, причем попарно.
3. Если в процессе сравнивания int i > int i+1, элементы меняются местами. В противном случае система переходит к сравнению следующей пары компонентов.

Больше ничего делать не придется. Данный алгоритм будет выполняться до тех пор, пока массив не будет отсортирован по возрастанию. Чтобы лучше понять его реализацию, можно попытаться воспользоваться им относительно числовой цепочки, написанной на бумаге. Если значение «справа» меньше, чем слева, соответствующие элементы меняются местами.

Пример программы на C

The bubble sort (алгоритм «пузырька») может быть применен в приложениях на самых разных языках программирования. Пример – на C. Создать код для изучаемого алгоритма сможет даже начинающий разработчик. Во всех языках программирования процедура будет одинаковой:

1. Сначала нужно сформировать несколько For-циклов (2). Они необходимы для того, чтобы программа проходила по всем элементам заданного массива N-раз. N – это размер массива.
2. Воспользоваться оператором ветвления If для сравнения ячеек в массиве данных.
3. Поменять местами сравниваемые значения, если элемент «справа» меньше, чем «слева».

Ниже представлен код приложения, использующий the bubble algorithm на языке C. Сначала нужно заполнить массив данными, а затем – сортировать его:

Теперь этот фрагмент можно разобрать более подробно.

Комментарии к коду

Чтобы лучше понимать предложенный код (и сам алгоритм «пузырька»), необходимо учитывать следующие комментарии:

1. В строке 16 был создан первый цикл For. В 17 строке формируется второй For-цикл, но вложенный.
2. В 18 строке осуществляется процедура сравнения пары элементов. Если результат заданного условия положительный, значения соответствующих компонентов в массиве меняются местами. В противном случае приложение начинает сравнивать следующую пару элементов в цепочке.
3. В строке 19 создается переменная b. Она необходима для изменения значений ячеек digitals[i] и digitals[i+1] местами. Переменная b используется только при соблюдении условий изменения позиций компонентов в массиве при помощи the bubble sort C.

Выше можно увидеть результат, выданный программой при обработке изучаемого фрагмента кода.

Оптимизированная версия метода

А вот улучшенный (оптимизированный) вариант пузырькового метода:

Здесь:

1. В строке 17 было изменено условие внутреннего цикла на i < 10-(i+1). Это связано с особенностями первого полного прохода цикла по массиву. Самый большой компонент будет перемещен в конец заданной цепочки. Второй – перейдет на предпоследнюю ячейку за второй проход цикла и так далее. Внедренное новое условие помогает избежать дополнительного сравнивания элементов массива. После каждого «прохода» внешнего цикла по заданной цепочке отрезок внутреннего цикла уменьшается на 1.
2. Изначально даже после полной сортировки последовательности значений система продолжает сравнивать элементы массива. Чтобы избавиться от этой особенности, в строке 5 была объявлена булева переменная flag («флаг» или «флажок»). Еще на этапе инициализации этого компонента он получает значение true. Изменение на false осуществляется, если в 4 строке результат выполненной операции будет положительным. Допустимо объявление переменной flag типа int, а вместо true и false хранить в переменной значение 1 и 0 соответственно.
3. Для выхода из алгоритма в 9 строке проверяются несколько условий. Первое – если булева переменная имеет значение true, значит массив уже отсортирован полностью. Это указывает на возможность выхода из цикла. Для данной операции используется оператор break. Если значение flag равняется false, информационный массив сортируется далее.
4. В 6 строке имеется новая функция – swap. Она принимает два значения, написанных через запятую, а затем меняет их местами. В приведенном примере swap принимает ячейки digitals[j] и digitals[j+1]. Эта функция используется для создания более компактного исходного кода приложения. Быстрее алгоритм работать не будет, поэтому использовать swap является необязательной функцией.

Теперь понятно, что собой представляет сортировка методом пузырька на C. Лучше изучить эту концепцию, а также научиться применять ее на практике помогут дистанционные компьютерные курсы. На них в срок от нескольких месяцев до года получится изучить разнообразные IT-направления, освоить инновационные профессии, а также научиться сортировать данные, причем не только пузырьковым методом. В конце обучения каждый успешно завершивший курс получит цифровой сертификат, подтверждающий приобретенные знания и умения.

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!