Содержание:

1. Реализация сортировки пузырьком: замеры производительности
2. Сферы применения алгоритма сортировки пузырьком  

Существует множество различных типов сортировки массивов: выбором, распределением, слиянием, вставками, обменами. У каждого типа существует множество различных реализаций и в данной статье мы рассмотрим наиболее известный пример реализации сортировки обменами – сортировку пузырьком.

Название описывает суть алгоритма в полной мере – каждый элемент массива представляется пузырьком, лёгкие всплывают к вершине массива, тяжёлые опускаются на дно массива.

Алгоритм состоит из следующих этапов:

1. Обход массива с нулевого индекса по последний индекс.
2. Если текущий элемент больше следующего, то они меняются местами, иначе остаются на своих местах.

Алгоритмическая сложность сортировки пузырьком является квадратичной, то есть O(n²).

Приступим к реализации данного алгоритма.

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

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

         Функция ПузырьковаяСортировка(Массив)

                   Возврат Массив;

         КонецФункции

Далее реализуем сам алгоритм сортировки, создадим двойной цикл, проходящийся по элементам массива и меняющий местами элементы

         Функция ПузырьковаяСортировка(Массив)

     Для а = 0 По Массив.ВГраница() Цикл

         Для б = 0 По Массив.ВГраница() – а – 1 Цикл

              Если Массив[б] > Массив[б+1] Тогда

                   ВрЭлемент = Массив[б];

                   Массив[б] = Массив[б+1];

                   Массив[б+1] = ВрЭлемент;

              КонецЕсли;

         КонецЦикла;

     КонецЦикла;

     ВремяИсполнения = Т;

     Возврат Массив;

КонецФункции

Проверим работоспособность написанной функции. Заполним массив 100 случайных элементов, значением от 0 до 100:

Неотсортированный массив

И отсортируем его:

Отсортированный массив

Как видно, сортировка отработала корректно.

Однако, не стоит забывать про квадратичную сложность данного алгоритма. Проверим сколько времени занимает сортировка массива, длинной всего в 100 элементов:

Сервер(файловый вариант):(19)

Сортировка заняла 0,2 секунды. Теперь увеличим количество элементов до 1000 и отсортируем их:

Сервер(файловый вариант):(17)

Сортировка заняла 21 секунду.

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

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

Специалист компании ООО “Кодерлайн”,

Астанов Артём