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

4 апреля 2021

Содержание

Реализация на Kotlin
Реализация на Java

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

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

На первой итерации в конце оказался наибольший элемент, однако надо отсортировать и другие. Поэтому возвращаемся в начало и начинаем новую итерацию. То есть мы проходимся по массиву много раз. Отсюда сложность алгоритма O(N^2), т.е. количество операций примерно равно количеству элементов массива в квадрате.

Рассмотрим реализацию этого алгоритма сначала на Kotlin, а затем и на Java.

Реализация на Kotlin

Для начала инициализируем исходный массив целых чисел с помощью метода intArrayOf().

fun main() {
    val array = intArrayOf(5, 2, 6, 7, 9, 6, 1, 8, 4)
    println(array.toList())
    array.bubbleSort()
    println(array.toList())
}

Преобразование массива в список делаем исключительно для того, чтобы метод println() корректно отобразил содержимое массива.

Сам метод bubbleSort() сделаем как метод расширения класса IntArray:

fun IntArray.bubbleSort() {
    var sorted = false
    while (!sorted) {
        // ...вложенный цикл...
    }
}

Заводим специальный флажок sorted, который является признаком того, что сортировка завершена. Затем запускаем цикл while, который на каждой итерации будет проверять состояние этого флажка. То есть цикл выполняется до тех пор, пока массив полностью не отсортирован.

Внутри этого цикла делаем ещё один цикл:

// начало цикла while
sorted = true
for (i in 1 until this.size) {
    val previous = this[i - 1]
    val current = this[i]
    if (previous > current) {
        this.swap(i - 1, i)
        sorted = false
    }
}
// конец цикла while

Перед началом вложенного цикла устанавливаем наш флаг в значение true. Затем проходимся по всем элементам, начиная со второго и до конца. На каждой итерации вложенного цикла берём текущий и предыдущий элемент и сравниваем их между собой. Если предыдущий больше текущего, то меняем их местами с помощью вспомогательного метода swap(). После обмена устанавливаем флаг sorted в false, чтобы внешний цикл затем пошёл ещё на одну итерацию.

Реализация вспомогательного метода swap() довольно проста. Он также выполнен как метод расширения класса IntArray:

fun IntArray.swap(index1: Int, index2: Int) {
    val buffer = this[index1]
    this[index1] = this[index2]
    this[index2] = buffer
}

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

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

Как видите, исходный массив был полностью отсортирован.

Реализация на Java

Теперь приведу полностью аналогичную реализацию алгоритма на Java 11. Метод main():

public static void main(String[] args) {
    var array = new int[]{5, 2, 6, 7, 9, 6, 1, 8, 4};
    System.out.println(Arrays.toString(array));
    bubbleSort(array);
    System.out.println(Arrays.toString(array));
}

Метод с пузырьковой сортировкой:

private static void bubbleSort(int[] array) {
    var sorted = false;
    while (!sorted) {
        sorted = true;
        for (var i = 1; i < array.length; i++) {
            var previous = array[i - 1];
            var current = array[i];
            if (previous > current) {
                swap(array, i - 1, i);
                sorted = false;
            }
        }
    }
}

Метод обмена значений:

private static void swap(int[] array, int index1, int index2) {
    var buffer = array[index1];
    array[index1] = array[index2];
    array[index2] = buffer;
}

Как видите, тут уже никаких методов расширения, поэтому приходится передавать в методы на один параметр больше. В остальном всё то же самое, только объём кода чуть больше.

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

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

Содержание

Реализация на Kotlin

Реализация на Java

Облако тэгов

Последние статьи

Комментарии

Добавить комментарий