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

Вступление

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

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

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

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

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

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

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

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

Как вы можете видеть, само название происходит от визуальной иллюзии элементов, “пузырящихся” в нужном месте. Если вы следуете определенному элементу, скажем, 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] в данной итерации, флаг отсортирован никогда не сбрасывается на 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 возвращаемого значения абсолютно допустимо при сортировке массивов, и содержимое не копируется по номинальной стоимости при использовании его в качестве аргумента. В этом случае массив сортируется “на месте”.

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

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

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

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 . Мы также можем @Переопределить метод toString () , если мы хотим распечатать результаты, но для краткости давайте не будем делать этого здесь и просто используем метод getId() вместо этого.

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

Git Essentials

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

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

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

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

public void bubbleSortArrayList(List 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 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 для элементов, которые мы хотим отсортировать позже.

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

public class Element implements Comparable {
    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 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 коллекций использует QuickSort для сортировки данной коллекции. Это приводит к огромным преимуществам производительности по сравнению с сортировкой пузырьков, но мы сохраним это для другой статьи.

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

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

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

List 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.588520		Первый запуск
0.664736		Второй заход
0.574807		Третий заход
0.526622		Четвертый прогон
0.522961		Пятый прогон
0.503327		Шестой прогон
0.504449		Седьмой прогон
0.640919		Восемь Пробегов
0.602143		Девятый прогон
0.694294		Десятый прогон

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

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

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

Вывод

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

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

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