Вступление
Сортировка - важный аспект обработки данных. Для нас, людей, гораздо естественнее сортировать вещи, которые имеют что-то общее, например, дату публикации, алфавитный порядок, статьи, принадлежащие автору, от наименьшего к наибольшему и т. Д.
Это значительно упрощает понимание данных, поскольку они логически связаны, а не рассредоточены по всему миру.
Сортировка человеком интуитивно понятна и проста, а потому часто неэффективна. Обычно мы не работаем более чем с двумя элементами, которые хотим отсортировать. Компьютеры могут хранить огромные объемы данных и местоположений элементов в своей памяти, что позволяет им сортировать коллекции так, как не могут люди, не говоря уже о скорости доступа / перемещения элементов.
Пузырьковая сортировка
Пузырьковая сортировка , в большинстве случаев, является первым алгоритмом сортировки, с которым столкнется любой энтузиаст информатики. Это самые простые и интуитивно понятные алгоритмы сортировки, что является одной из основных причин, по которой им обучают начинающих программистов / студентов.
Он работает, меняя местами соседние элементы в соответствии с критериями заказа. Например, если мы хотим отсортировать элементы коллекции от наименьшего к наибольшему - если первый элемент больше второго, они меняются местами. Этот простой обмен повторяется со смежными индексами до тех пор, пока коллекция в конечном итоге не будет отсортирована.
Условие выхода для алгоритма - это когда мы перебираем всю коллекцию, не меняя местами ни одного элемента, что означает, что она полностью отсортирована.
Вот визуальное представление того, как работает пузырьковая сортировка:
{.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 коллекций встроены гораздо более эффективные алгоритмы, мы бы посоветовали вам не использовать этот алгоритм для каких-либо производственных приложений.