Пузырьковая сортировка в Java

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

Вступление

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

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

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

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

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

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

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

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

анимация анимация пузырьковаясортировка{.ezlazyload}

Как видите, само название происходит от визуальной иллюзии, что элементы «пузыряются» в желаемое место. Если вы проследите за определенным элементом, скажем, 8 - вы можете заметить, что он «всплывает» в нужное место в этом примере.

Выполнение

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

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

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

 public void bubbleSort(int[] array) { 
 boolean sorted = false; 
 int temp; 
 while (!sorted) { 
 sorted = true; 
 for (int i = 0; i < array.length - 1; i++) { 
 if (a[i] > a[i+1]) { 
 temp = a[i]; 
 a[i] = a[i+1]; 
 a[i+1] = temp; 
 sorted = false; 
 } 
 } 
 } 
 } 

sorted используется, чтобы сигнализировать, отсортирован массив или нет. Если нет причин менять местами какой-либо элемент, или, скорее, a[i] всегда меньше, чем a[i+1] в данной итерации, sorted никогда не сбрасывается в false .

Поскольку он остается true , массив сортируется, и мы выходим из цикла.

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

 int[] array = new int[]{5, 6, 7, 2, 4, 1, 7}; 
 bubbleSort(array); 
 System.out.println(Arrays.toString(array)); 

Будет давать:

 [1, 2, 4, 5, 6, 7, 7] 

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

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

Более распространенным сценарием будет сортировка ArrayList заполненного нечисловыми объектами. Это могут быть сотрудники, результаты из базы данных, пользователи и т. Д. Поскольку мы заранее не знаем, как сортировать эти объекты, это должно быть предоставлено вызывающей стороной через метод comapreTo() .

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

 public class Element { 
 private int id; 
 
 public Element(int id) { 
 this.id = id; 
 } 
 
 // Getters and setters 
 
 public int compareTo(Element element) { 
 int res = 0; 
 if (this.id < element.getId()) { 
 res =- 1; 
 } 
 if (this.id > element.getId()) { 
 res = 1; 
 } 
 return res; 
 } 
 } 

Это очень простой класс с одним полем - id . Мы также можем @Override метод toString() если мы хотим распечатать результаты, но для краткости давайте не будем делать этого здесь и просто используем вместо этого метод getId()

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

Теперь наш compareTo() просто сравнивает id s и возвращает -1 если id текущего элемента меньше, чем элемент, с которым мы его сравниваем, 1 если id текущего элемента больше, или 0 если они равны.

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

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

 public void bubbleSortArrayList(List<Element> list) { 
 Element temp; 
 boolean sorted = false; 
 
 while (!sorted) { 
 sorted = true; 
 for (int i = 0; i < list.size()-1; i++) { 
 if (list.get(i).compareTo(list.get(i + 1)) > 0) { 
 temp = list.get(i); 
 list.set(i, list.get(i + 1)); 
 list.set(i + 1, temp); 
 sorted = false; 
 } 
 } 
 } 
 } 

Это довольно простой код, практически такой же, как код в примере с массивами, использующий методы, предоставляемые интерфейсом List

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

 List<Element> list = new ArrayList<>(); 
 
 // Create elements w/ IDs 0-24 
 for (int i = 0; i < 25; i++) { 
 list.add(new Element(i)); 
 } 
 
 // Move the elements to a random order 
 Collections.shuffle(list); 

И мы можем отсортировать это:

 // Print list before sorting 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 
 
 // Sort the list 
 bubbleSort.bubbleSortArrayList(list); 
 
 System.out.println(); 
 
 // Print sorted list 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 

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

 17, 13, 14, 5, 15, 22, 24, 7, 3, 9, 21, 10, 1, 11, 18, 20, 12, 8, 4, 19, 0, 23, 16, 2, 6, 
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 

API коллекций

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

Давайте изменим наш Element так, чтобы он реализовал интерфейс Comparable

 public class Element implements Comparable<Element> { 
 private int id; 
 
 // Constructor, getters and setters 
 
 @Override 
 public int compareTo(Element element) { 
 int res = 0; 
 if (this.id < element.getId()) { 
 res =- 1; 
 } 
 if (this.id > element.getId()) { 
 res = 1; 
 } 
 return res; 
 } 
 } 

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

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

 List<Element> list = new ArrayList<>(); 
 for (int i = 0; i < 10000; i++) { 
 list.add(new Element(i)); 
 } 
 
 Collections.shuffle(list); 
 
 // Print shuffled list 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 
 
 // Sort the list 
 Collections.sort(list); 
 
 System.out.println(); 
 
 // Print sorted list 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 

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

Сложность времени

Временная сложность (как средняя, так и наихудшая) пузырьковой сортировки составляет O (n ^ 2) . Это ужасно для алгоритма сортировки.

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

 List<Element> list = new ArrayList<>(); 
 for (int i = 0; i < 10000; i++) { 
 list.add(new Element(i)); 
 } 
 
 Collections.shuffle(list); 
 
 // Print shuffled collection 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 
 
 long startTime = System.nanoTime(); 
 bubbleSort.bubbleSortArrayList(list); 
 long endTime = System.nanoTime(); 
 
 // Print sorted collection 
 list.forEach(e -> System.out.print(e.getId() + ", ")); 
 
 System.out.println(); 
 
 // Print runtime in nanoseconds 
 System.out.println("Bubble Sort runtime: " + (endTime - startTime)); 

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


Пузырьковая сортировка время (с)
Первый забег 0,5885202
Второй прогон 0,6647364
Третий пробег 0,5748066
Четвертый забег 0,5266222
Пятый заезд 0,522961
Шестой пробег 0,5033268
Седьмой забег 0,5044489
Восьмерка 0,6409187
Девятый забег 0,6021427
Десятый забег 0,694294


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

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

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

Заключение

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

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

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

comments powered by Disqus