сортировка пузырьком java код

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

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

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

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

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

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

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

Допустим, изначально у нас есть массив на 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], то есть при отсутствии обменов. Вот так вот.

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

Источник

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

Пузырьковая сортировка в большинстве случаев является первым алгоритмом сортировки, с которым вы столкнетесь. В этой статье мы глубоко погрузимся в алгоритм, в то, как он работает, а затем реализуем его на Java.

Вступление

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

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

Сортировка людей интуитивно понятна и проста, и поэтому часто неэффективна. Обычно мы работаем не более чем с двумя элементами, которые хотим отсортировать. Компьютеры способны хранить в своей памяти огромные объемы данных и расположения элементов, что позволяет им сортировать коллекции так, как люди не могли бы, не говоря уже о скорости доступа/перемещения элементов.

Сортировка Пузырьков

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

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

Условие выхода для алгоритма – это когда мы перебираем всю коллекцию, не меняя местами ни одного элемента, что означает, что она полностью отсортирована.

Вот наглядное представление того, как работает сортировка пузырьков:

Как вы можете видеть, само название происходит от визуальной иллюзии элементов, “пузырящихся” в нужном месте. Если вы следуете определенному элементу, скажем, 8 – вы можете заметить, как он “пузырится” в правильном месте в этом примере.

Реализация

Сортировка Массивов

Давайте начнем с сортировки простого массива целых чисел:

Запуск этого фрагмента кода:

Примечание: Поскольку массивы в Java рассматриваются как объекты, наличие типа void возвращаемого значения абсолютно допустимо при сортировке массивов, и содержимое не копируется по номинальной стоимости при использовании его в качестве аргумента. В этом случае массив сортируется “на месте”.

Сортировка списков массивов

Давайте определим класс для наших объектов, которые будут храниться в коллекции:

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

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Действительно, вы можете реализовать функцию сравнения любым удобным для вас способом.

Теперь давайте снова реализуем сортировку по пузырькам:

Теперь давайте заполним ArrayList несколькими элементами:

И мы можем это уладить:

Как и ожидалось, результат будет:

API коллекций

Отличительной особенностью API коллекций, поставляемого с Java 8, являются вспомогательные методы, которые позволяют быстро и легко сортировать коллекции. Нам просто нужно реализовать интерфейс Comparable для элементов, которые мы хотим отсортировать позже.

Давайте изменим наш Элемент класс так, чтобы он реализовывал Сопоставимый интерфейс:

Как вы можете видеть, класс Element практически такой же, как и раньше. На этот раз мы реализовали интерфейс Comparable и переопределили его метод compareTo() с той же логикой, что и раньше.

Теперь мы можем просто вызвать Collections.sort() в нашем списке:

Метод sort() из API коллекций использует QuickSort для сортировки данной коллекции. Это приводит к огромным преимуществам производительности по сравнению с сортировкой пузырьков, но мы сохраним это для другой статьи.

Временная Сложность

Хотя и ужасно, вот как работает алгоритм при сортировке 10,000 объекты в коллекции:

И вот результаты через несколько секунд после запуска 10 раз:

При среднем времени выполнения

0,5 с для 10 000 объектов вам действительно понадобятся алгоритмы, которые работают лучше? В большинстве случаев, на самом деле, нет, если только у вас нет приложения с высокой нагрузкой, которое требует быстрого времени отклика.

Если вы проводите более сложные сравнения, чем просто сравнение id s, и у вас огромная коллекция, намного больше, чем эта, – да, использование продвинутого алгоритма с гораздо большей временной сложностью значительно повлияет на вашу производительность.

Для справки, метод sort() из API коллекций последовательно отсортировал этот же массив из 10 000 элементов всего за 0,01 секунды. Поэтому, даже если нет реальной необходимости сортировать ваши коллекции быстрее 0,5 с, использование встроенного сортировщика, предоставляемого API коллекций, сэкономит вам время при написании кода и улучшит ваше приложение.

Вывод

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

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

Это ужасно неэффективно, и, учитывая, что в API коллекций Java встроены гораздо более эффективные алгоритмы, мы бы посоветовали вам не использовать этот алгоритм для каких-либо производственных приложений.

Источник