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

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

Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.

Сортировка выбором (Selection sort) в Java.

Реализация алгоритма Сортировка выбором на Java:

Еще одним достаточно простым и известным способом сортировки является Сортировка пузырьком.

Сортировка пузырьком (Bubble sort) в Java.

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

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

Следующие 2 видео наглядно демонстрируют работу алгоритмов сортировки пузырьком и выбором.

Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:

Или мы можем создать массив случайных чисел

Затем воспользуемся вышеприведенными алгоритмами сортировки

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

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

Сортировка массива при помощи метода sort() из класса Arrays.

Метод sort() из класса Arrays использует усовершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку.

Примечание: в начале файла предварительно нужно подключить библиотеку java.util.

Сортировка массива целых чисел по возрастанию:

Сортировка массива целых чисел по убыванию:

Обратите внимание, что при сортировке массива в обратном порядке (по убыванию) нужно использовать тип Integer[] вместо примитивного типа int[].

Сортировка массива строк в Java:

В этом примере массив имен сортируется в порядке от А до Я. Для того чтобы отсортировать массив в обратном порядке, необходимо в методе sort() указать Collections.reverseOrder().

К сожалению, по умолчанию метод sort() сортирует только примитивные типы данных и строки. Как сортировать массив из собственно созданных объектов, будет рассмотрено в следующих уроках, поскольку это требует более углубленных знаний.

Нужно создать сортировку массива методом пузырька, когда пузырек "тонет" (с конца массива до начала, НЕ сортировка по убыванию) В чем проблема? Вот мой код:

Читайте также:  Sony vaio vpc y21m1r

Результат вывода на экран:

Почему не правильно проходит сортировка? Подскажите, пожалуйста!

1 ответ 1

Давайте для начала напишем обычный канонический пузырёк.

Если уже решили оптимизировать, то

Уже тут видно, что else break ломает всё.

Дальше мы хотим делать это с конца. Окей. Первый цикл вообще (!) ни на что не влияет, хоть с конца идти, хоть сначала, поэтому так и оставим. Второй надо развернуть. Если развернуть в лоб – будет совсем некрасиво. Меняем порядок обхода в j+1 на j-1 Получается в целом нормально

Изучение алгоритмов сортировки на языке Java поможет не изобретать велосипеды и быстро выскочить на лесенку карьерного роста.

Задействование алгоритмов сортировки поможет нам упорядочить массивы Java. Для понимания: сортировка чисел от наименьшего к большему или наоборот, а также лексикографический порядок – это примеры алгоритмов сортировки, способные упорядочить Java строки и числа

Слышали о сортировке пузырьком? Его популярность обусловлена простотой, наглядностью и, конечно, названием.

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

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

Вот шаги для сортировки массива чисел от наименьшего к большему:

  • 4 2 1 5 3 : два первых элемента расположены в массиве в неверном порядке. Меняем их.
  • 2 4 1 5 3 : вторая пара элементов тоже «не в порядке». Меняем и их.
  • 2 1 4 5 3 : а эти два элемента в верном порядке (4 2 1 4 5 3 : очередная замена.
  • 2 1 4 3 5 : результат после одной итерации.

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

Но причём тут пузырьки? Посмотрите снова на пример, и вы увидите, что алгоритм как бы смещается вправо. По этому поведению элементов в массиве и возникла аналогия с «пузырьками», всплывающими на «поверхность».

Реализация

Функция входит в цикл while , в котором проходит весь массив и меняет элементы местами при необходимости.

Массив в алгоритме считается отсортированным. При первой замене доказывается обратное и запускается еще одна итерация.

Цикл останавливается, когда все пары элементов в массиве пропускаются без замен:

Будьте осторожны с формулировкой условия замены!

Например, при условии a[i] >= a[i+1] алгоритм войдет в бесконечный цикл, потому что для равных элементов это условие остается true : отсюда следует бесконечная замена

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

Рассмотрим наихудший сценарий. Вот в чем вопрос: сколько итераций нужно для сортировки всего массива? Пример:

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

Расширьте это утверждение для массива из n элементов, и получите n итераций. В коде это означает, что цикл while будет запускаться максимум n раз.

Каждая n-ая итерация по всему массиву (цикл for в коде) означает, что временная сложность в наихудшем случае будет равна O(n ^ 2).

Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.

Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.

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

В приведенном ниже массиве жирная часть отсортирована в порядке возрастания. Посмотрите что произойдет в этом случае:

  • 3 5 7 8 4 2 1 9 6 : выбираем 4 и помним, что это элемент, который нужно вставить. 8 > 4, поэтому сдвигаем.
  • 3 5 7 x 8 2 1 9 6 : здесь x – нерешающее значение, так как элемент будет перезаписан (на 4, если это подходящее место, или на 7, если смещение). 7 > 4, поэтому сдвигаемся.
  • 3 5 x 7 8 2 1 9 6
  • 3 x 5 7 8 2 1 9 6
  • 3 4 5 7 8 2 1 9 6
Читайте также:  Asrock p67 fatality professional

Теперь вы видите, что отсортированная часть дополнилась элементом. Каждая следующая итерация делает то же самое, и к концу вы получите отсортированный массив!

Реализация

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

Вернемся к худшему сценарию – к массиву, отсортированному в убывающем порядке.

В этом случае каждая итерация сдвигает отсортированный массив на единицу O(n). Придется делать это для каждого элемента в каждом массиве, что приведет к сложности равной O(n ^ 2).

Сортировка выбором тоже разделяет массив на сортированный и несортированный подмассивы. Но на этот раз сортированный подмассив формируется вставкой минимального элемента не отсортированного подмассива в конец сортированного, заменой:

  • 3 5 1 2 4
  • 1 5 3 2 4
  • 1 23 5 4
  • 1 2 3 5 4
  • 1 2 3 45
  • 1 2 3 45

Реализация

В каждой итерации вы предполагаете, что первый неотсортированный элемент минимален и итерируете по всем оставшимся элементам в поисках меньшего.

После нахождения текущего минимума неотсортированной части массива вы меняете его местами с первым элементом, и он уже часть отсортированного массива:

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

При поиске минимума для длины массива проверяются все элементы, поэтому сложность равна O(n). Поиск минимума для каждого элемента массива равен O(n^2).

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

Массив делится на два подмассива, а затем происходит:

  1. Сортировка левой половины массива (рекурсивно)
  2. Сортировка правой половины массива (рекурсивно)
  3. Слияние

На схеме показана работа рекурсивных вызовов. Для массивов, отмеченных стрелкой вниз, вызывается функция. Во время слияния возвращаются массивы со стрелкой вверх. Всё просто: мы следуем за стрелкой вниз к нижней части дерева, а затем возвращаемся и объединяем.

В примере массив 3 5 4 2 1 делится на 3 5 4 и 2 1 и так далее. При достижении «дна» начинается объединение и сортировка.

Реализация

В главную функцию передаются left и right – индексы подмассивов для сортировки, крайние слева и справа. Изначально они имеют значения 0 и array.length-1 , в зависимости от реализации.

Основа нашей рекурсии гарантирует, что мы выйдем, когда закончим, или когда left и right встретятся друг с другом. Мы находим среднюю точку mid и рекурсивно сортируем подмассивы слева и справа от середины, в итоге объединяя наши решения.

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

Достаточно следовать индексам не нарушая логики дерева рекурсии:

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

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

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

Хотите легко рассчитывать рекурсивные реализации алгоритмов сортировки? Приготовьтесь к математике 🙂

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

Здесь a – это количество меньших рекурсивных вызовов, на которые мы делим проблему, а b указывает на входную величину рекурсивных вызовов.

Остальная часть уравнения – это сложность слияния всех решений в одно конечное. Упомянутая теорема решит все за вас:

Если T(n) – это время выполнения алгоритма для сортировки массива длинной n , сортировка слиянием запустится дважды для массивов длиной вполовину от оригинального.

Так, если a=2 , b=2 , шаг слияния занимает O(n) памяти при k=1 . Это означает, что уравнение для сортировки слиянием будет выглядеть так:

Читайте также:  Как подключить новый джойстик к xbox one

Примените теорему, и вы увидите, что в нашем случае a=b^k , ибо 2=2^1 . Значит, сложность равна O(nlog n), и это лучшая временная сложность для алгоритма сортировки. Доказано, что массив не может быть отсортирован быстрее, чем O(nlog n).

Для понимания работы пирамидального алгоритма сортировки нужно понять структуру, на которой он основан – пирамиду.

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

По мере движения вниз по дереву значения уменьшаются (min-heap) или увеличиваются (max-heap). Смотрите пример max-heap:

А теперь представим пирамиду в виде массива:

Чтение графа сверху вниз здесь представлено слева направо. Мы добились того, что позиция дочернего элемента по отношению к k -ому элементу в массиве – 2*k+1 и 2*k+2 (при условии, что индексация начинается с ). Проверьте сами!

И наоборот, для k -го элемента дочерняя позиция всегда равна (k-1)/2 .

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

Условие верно? Тогда меняйте местами один из дочерних элементов с родительским и повторяйте рекурсию с новым родительским элементом (он может всё ещё быть больше другого дочернего).

  • 6 1 8 3 5 2 4 : оба дочерних меньше родительского, оставляем как есть.
  • 6 1 8 3 5 2 4 : 5 > 1, поэтому меняем их. Теперь рекурсивно проверяем 5.
  • 6 5 8 3 1 2 4 : оба дочерних меньше 5, поэтому пропускаем.
  • 65 8 3 1 2 4 : 8 > 6, поэтому меняем их.
  • 8 5 6 3 1 2 4 : мы получили пирамиду, изображенную выше!

Вы научились строить пирамиду из массива, все остальное гораздо проще! Поменяйте местами корень пирамиды с концом массива, и сократите массив на единицу.

Постройте кучу из сокращенного массива и повторяйте процесс:

  • 8 5 6 3 1 2 4
  • 4 5 6 3 1 2 8 : замена
  • 6 5 4 3 1 28 : сортировка
  • 2 5 4 3 1 6 8 : замена
  • 5 2 4 2 16 8 : сортировка
  • 1 2 4 2 5 6 8 : замена

И так далее. Видите закономерность?

Реализация

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

Посмотрите на функцию heapify() – кажется, что все делается за O(1), верно? Но нет же: все портит рекурсивный вызов!

Готовы посчитать, сколько вызовов нужно в наихудшем сценарии? В худшем случае рекурсивный вызов дойдет до самой вершины пирамиды прыжками к родителям каждого узла в отношении i/2 . Всего потребуется log n прыжков до вершины, значит, сложность равна O(log n).

В связи с циклами for , которые итерируют весь массив, сложность heapSort() равна O(n). Это дает нам суммарную сложность пирамидальной сортировки O(nlog n).

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

Перед вами очередной алгоритм техники «разделяй и властвуй». Он выбирает один элемент массива в качестве стержня и сортирует остальные элементы вокруг (меньшие элементы налево, большие направо).

Так соблюдается правильная позиция самого «стержня». Затем алгоритм рекурсивно повторяет сортировку для правой и левой частей.

Реализация

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

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

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

Получается O(n^2).

На фоне алгоритмов сортировки со сложностью O(nlog n), выглядит не очень 🙁

На практике быстрая сортировка применяется широко. Судите сами: у алгоритма очень хорошее среднее время запуска, также равное O(nlog n), он эффективен для больших потоков ввода. И на этом преимущества не заканчиваются!

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

На этом всё! Не пропустите книги по Java, среди которых Алгоритмы на Java – Роберт Седжвик, Кевин Уэйн – полезная книга для дальнейшего погружения в тему.