Сортировка пузырьком в Java

Данная статья написана командой Vertex Academy. Это одна из статей из нашего Самоучителя по Java.

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

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

Как работает сортировка пузырьком?

Сортировка пузырьком заключается в следующем:

• начиная с начала массива просматриваем попарно по 2 элемента (первый со вторым, второй с третим, третий с четвертым и т.д.).
• Если второй элемент в паре меньше первого элемента – перемещаем его на место первого, а первый на место второго. Это мы делаем для всех элементов.
• После того, как мы дошли до конца массива (сравнили предпоследний и последний элементы и сделали обмен, если нужно), проверяем, был ли хотя бы один обмен. Если да, значит массив не отсортирован и начинаем все сначала. Повторяем такие проходы, пока не будет так, что мы проверили попарно все элементы от начала до конца, а обмена ни одного не было. Таким образом элементы с самыми маленькими значениями потихоньку перемещаются справа налево. То есть они как будто всплывают, как мыльный пузырь. Отсюда и название метода – пузырьком.

Рассмотрим данный способ на примере.

Допустим, изначально у нас есть массив на 5 элементов [4, 1, 6, 9, 2].

Как видите, массив изначально не отсортирован. Поэтому начинаем первый проход.

На видео видно, что:

1. Мы сравнили первый элемент – 4 – и второй элемент – 1. Поскольку 1 меньше 4, мы делаем обмен. Теперь первый элемент 1, второй – 4.

2. Дальше сравниваем уже новый второй элемент и третий, то есть 4 и 6. Очевидно, что 4 меньше 6. И в данном случае элементы не меняются местами, потому что слева должен стоять элемент с меньшим значением, а 4 и так у нас уже стоит левее, чем 6.

3. И далее таким способом мы проходим до конца массива. В конце прохода мы получим массив [1, 4, 6, 2, 9]. Однако наш массив все еще не отсортирован должным образом, поэтому повторяем проход.

При этом проходе мы сделали то же самое, что и в первый раз – сравнили попарно все элементы, сделали все необходимые обмены. В результате получили следующий массив: [1, 4, 2, 6, 9]. Уже сейчас можно проследить, что число 2 с каждым проходом сдвигается на 1 позицию влево. В этом и есть вся суть метода пузырьком – смещать элементы с меньшими значениями влево, а элементы с бОльшими значениями смещать вправо.

И все еще массив не отсортирован должным образом, поэтому повторяем проход.

После прохода мы получили массив [1, 2, 4, 6, 9]. Ну что, пройдем еще разочек по массиву?

Собственно, проверка показывает, что вот теперь массив отсортирован. Ура, товарищи джависты! Мы достигли цели и отсортировали массив. Теперь можно отдохнуть и выпить чего-то согревающего (кофе, например).

Рассмотрим реализацию алгоритма сортировки пузырьком на Java

Допустим у нас есть массив, который мы хотим отсортировать по возрастанию (от меньшего значения к большему). Реализация на Java будет выглядеть вот так:

Собственно говоря, вот что мы написали в коде:

1. Сначала мы создали массив mas, который хотим отсортировать.

2. Далее создали переменную isSorted, которая будет таким себе флажком того, отсортирован ли уже массив или нет.

3. На следующей строчке мы создали переменную buf, которая нам пригодится при обмене.

4. Собственно, далее создали цикл, который будет делать проход за проходом. Так, как мы не знаем, сколько циклов нужно сделать, то использовали цикл while. Если призабыли, какие есть циклы в Java, почитайте нашу статью о циклах в Java. В худшем случае (элемент с самым маленьким значением находится в конце) нам придется сделать столько проходов, сколько элементов в массиве. В лучшем случае, то есть если массив изначально уже отсортирован, мы сделаем один единственный проход для того, чтобы убедиться, что ни одного обмена не было.

Первым действием в цикле будет установка значения в true, то есть изначально мы предполагаем, что массив отсортирован. А дальше нам нужно попарно сравнить все элементы массива. Соответственно, нам нужно использовать еще один цикл внутри внешнего. В этом случае мы точно знаем, сколько итераций будет, поэтому используем цикл for. Обратите внимание, что правая граница не на mas.length, а mas.length – 1, поскольку мы сравниваем i-й и i+1-й элементы, и чтобы мы не вышли за пределы массива, делаем на 1 цикл меньше.

В цикле for проверяем, больше ли i-й элемент, чем элемент i+1. Если да, то устанавливаем флажек отсортированости в false (есть обмен, поэтому массив все еще не отсортирован). Далее делаем обмен через созданную ранее переменную buf. Собственно, все. Таким образом, цикл while будет работать, пока переменная isSorted будет в положении false на момент окончания попарной проверки. А это возможно только при отсутствии ситуаций, когда mas[i] > mas[i + 1], то есть при отсутствии обменов. Вот так вот.

Кстати, если нужно отсортировать массив в обратном порядке, то есть от большего значения к меньшему, достаточно изменить одну единственную строчку (а точнее, поменять знак в ней):

Она будет выглядеть так:

В остальном все так же.

На этом все. Удачи!