Предварительные требования:
Некоторые базовые знания программирования на любом основном языке программирования, таком как Python, C++, Java и т. д. Знание асимптотических обозначений (см. эту статью) и способов их расчета (см. эту статью) для алгоритмов.
Предисловие:
Эта статья является первой частью серии «Алгоритмы». Алгоритмы сортировки — это класс алгоритмов, которые упорядочивают заданные входные данные в любом определенном порядке. Это помогает снизить время вычислений, необходимое для использования данных, поскольку данные расположены в определенном порядке. Сегодня мы поговорим о простом (но неэффективном) алгоритме сортировки Bubble Sort.
Объяснение:
Пузырьковая сортировка — очень популярный и простой алгоритм сортировки. Однако из-за своей простоты он также очень неэффективен. Тем не менее, это отличный способ начать свое путешествие в мир алгоритмов.
Если мы хотим отсортировать входные данные, скажем, в порядке возрастания, тогда он просто выбирает элемент и перемещает его вправо от списка входных данных до тех пор, пока следующий элемент справа не станет больше.
Отсюда и название пузырьковой сортировки, поскольку самый большой элемент «пузырится» до конца, точно так же, как самый большой пузырь из множества пузырьков поднимается наверх, а самый маленький оказывается внизу.
Поэтапную процедуру можно описать следующим образом:
- Выберите элемент.
- Сравните элемент с элементом справа.
- Если наш элемент больше, переместите его вправо и вернитесь к шагу 2. В противном случае ничего не делайте и вернитесь к шагу 2.
- Повторите для всех элементов.
Код:
Мы можем использовать эту пошаговую процедуру и написать код так:
BUBBLE_SORT(A): for i=0 upto A.size: for j=i upto A.size - 1: if A[j] > A[j+1]: swap A[j], A[j+1]
Вот объяснение кода:
for i=0 upto A.size:
Переменная «i» перемещается от 0 до A.size. Мы используем ее, чтобы наш алгоритм выполнил операцию для всех элементов (шаг 4).
for j=0 upto A.size - 1:
Переменная «j» изменяется от 0 до A.size — 1. Мы используем ее, чтобы выбрать элемент, который хотим сравнить (шаг 1).
if A[j] > A[j+1]: swap A[j], A[j+1]
Эта строка используется для сравнения элемента в позиции «j» с элементом в позиции «j+1», то есть следующим элементом (шаг 2). Если сравнение верно, то мы меняем местами два элемента, в противном случае мы просто выходим из цикла (шаг 3).
Производительность:
Теперь посчитаем временную сложность алгоритма.
Средний сценарий:
Первый цикл идет от i=0 до A.size, а второй цикл идет от j=0 до A.size-1. Поскольку оба цикла вложенные и зависят от размера массива A (назовем его N). Код будет иметь среднюю временную сложность ϴ(N²).
Наилучший сценарий:
Если массив A уже отсортирован, код будет выполняться как обычно, только оператор if внутри второго цикла не будет выполняться.
Следовательно, в лучшем случае временная сложность все равно будет равна Ω(N²).
Наихудший сценарий:
Если массив A полностью отсортирован, но совершенно противоположным образом, мы этого хотим. Тогда он также будет выполняться как обычно.
Следовательно, в наихудшем сценарии временная сложность все равно будет равна O(N²).