Сортировка «Bubble» и другие методы упорядочивания данных

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

Разработчики могут пользоваться алгоритмами, которые помогают упорядочивать разные неорганизованные данные. Соответствующие последовательности действий отличаются друг от друга. Этих алгоритмов очень много. Один из наиболее простых вариантов – пузырьковая сортировка массива.

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

Определение и принцип работы

Bubble Sort – один из квадратичных алгоритмов сортировки элементов массива. Он на каждом шаге берет два соседних значения и сравнивает их. Наибольший элемент ставится в конец соответствующей пары.

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

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

Работает bubble sort так:

1. Сначала берется самый первый элемент заданного массива и сравнивается со вторым. Если первый больше второго, нужно поменять их местами. В противном случае никаких изменений производить не придется.
2. Теперь берется второй элемент в массиве. Он сравнивается со следующим – третьим. Если второй компонент больше, они меняются местами.
3. Подобные операции сравнения и изменения положения элементов в массиве осуществляются до самой последней составляющей. В конце будет наибольшее число заданной последовательности.
4. Система возвращается в самое начало алгоритма. Все описанные ранее действия выполняются снова, начиная с первого и второго элемента. Разница заключается в том, что последний компонент проверять нет необходимости – он уже стоит на месте.
5. Как только заканчивается очередная итерация, значение финальной позиции, до которой осуществляется проверка, уменьшается. Алгоритм воспроизводится с новыми данными.
6. Описанные действия должны продолжаться до тех пор, пока не останется всего один элемент. Он окажется минимальным во всей заданной последовательности.

Предложенная концепция позволит упорядочить данные по возрастанию. Чем меньше окажется первоначальная последовательность чисел, тем быстрее будет работать метод.

Эффективность

Рассматриваемая концепция упорядочивания называется «учебной». Она присутствует в учебниках по математике и информатике, но в реальной жизни практически не встречается. Связано это с необходимым количеством проверок и перестановок в заданном неупорядоченном множестве. Соответствующее число – это количество элементов последовательности в квадрате. Пример – для 10 чисел нужно будет 100 проверок, для 100 – 10 0000 и так далее.

Программирование предусматривает оценку эффективности работы алгоритма в зависимости от количества элементов n. Обозначается она как O(n). Пузырьковая сортировка имеет эффективность O(n².). Если сравнивать этот показатель с некоторыми другими методами упорядочивания, он будет относительно большим. Это значит, что чем больше показатель эффективности, тем дольше алгоритм будет обрабатывать заданную последовательность.

Как реализуется

Теперь можно рассмотреть bubblesort на наглядном примере. Данная концепция хорошо реализуется во всех языках программирования. Ниже будет приведен фрагмент на Java. Этот язык выбран ввиду его широкого распространения.

Код программы имеет следующие особенности:

• формируется массив из 5-ти составляющих;
• в заданное множество загружаются числовые данные;
• на экране выводится содержимое массива;
• осуществляется bubble sort;
• происходит повторный вывод отсортированных цифровых материалов на экране.

Вот так будет выглядеть соответствующий фрагмент приложения. Его можно загрузить в IDE и посмотреть на результат:

Несмотря на наличие комментариев в коде, его лучше разобрать более подробно.

Разбор кода

В предложенном выше фрагменте основная работа сконцентрирована в классе ArrayBubble. Он включает в себя конструктор, а также несколько методов:

• printer – используется для построчного выведения массива на дисплей;
• into – метод, который используется для вставки компонентов в заданное неупорядоченное множество;
• toSwap – используется для переставления компонентов заданной последовательности местами в случае необходимости;
• dummy – временная переменная, в которую записывается значение числа, которое будет меняться местами со вторым значением
• bubbleSorter – ключевой метод, который осуществляет основную работу и сортирует данные, хранящиеся в неупорядоченном множестве.

Вот фрагмент bubbleSort. Он требует дополнительного разбора:

Особое внимание необходимо уделить двум счетчикам: out и in.

Внешний счетчик (out) отвечает за начало перебора значений с конца массива и постепенно уменьшается. С каждой новой итерацией первоначальное значение становится меньше на единицу. Переменная out будет смещаться в левую сторону. Это необходимо, чтобы не затрагивать значения, которые уже отсортированы в правой части последовательности.

Внутренний счетчик сортировки пузырьком (in) начинает перебор значений с самого начала и увеличивается на единицу. Происходит операция с каждой новой итерацией. In увеличивается до тех пор, пока не будет достигнут out – последний анализируемый на текущем проходе компонент). Внутренний цикл in сравнивает две соседние ячейки (in и in+1). Если в in хранится значение больше числа, размещенного в in+1, происходит вызов метода toSwap. Он поменяет параметры местами.

Прочие известные алгоритмы упорядочивания

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

Bubble Sort заложен в основу большинства других методов сортировки элементов. Вот наиболее распространенные из них:

1. Сортировка выбором. Концепция, которая сначала ищет наименьший элемент в заданной последовательности и ставит его на позицию, откуда начался проход. Далее предстоит передвинуться на следующую позицию.
2. Вставки. Концепция разделяет изначальное множество на сортированный и несортированный подмассив. Длина первой части в самом начале равна единице. Это соответствует левому (первому) значению в последовательности. Далее нужно итерировать множество и расширять сортированную часть. С каждым проходом цикла он увеличивается на +1. После расширения новый компонент помещается на свое место в подмассиве. Результат достигается при помощи сдвига всех составляющих вправо. Происходит это до тех пор, пока не встретится элемент, не требующий сдвига.
3. Пирамида. Чтобы понимать принцип работы этого вида сортировки, нужно разобраться в том, что собой представляет двоичная куча (пирамида). Это дерево, в котором каждый узел состоит в отношениях с дочерними узлами. Добавление нового узла начинается с левой позиции нижнего неполного уровня. По мере движения вниз по дереву значения уменьшаются (min-heap) или увеличиваются (max-heap). Чтение графа сверху-вниз представлено слева-направо.

Вот пирамида:

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

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