Мы продолжаем рассматривать простые сортировки. В этот раз рассмотрим сортировку пузырьком (bubble sort) и её модификации. К модификациям пузырьковой сортировки можно отнести сортировку перемешиванием или шейкерную сортировку, а также сортировку расческой.
Сортировка пузырьком
Сортировка пузырьком является, пожалуй, одним из самых известных алгоритмов сортировки. Этот алгоритм достаточно прост и понятен, очень часто именно с него начинается знакомство с алгоритмами сортировок в вузах и на различных курсах. Единственный вопрос, который может тут возникнуть: «Почему мы не рассмотрели его раньше?» 😊
А сам алгоритм работает так:
Он последовательно сравнивает значения соседних элементов и меняет их местами, если последующее оказывается меньше предыдущего. Таким образом, элементы с наибольшим значением перемещаются в конец массива. На рисунке ниже представлен Java-код этого алгоритма.
Как уже говорилось, алгоритм очень простой, и как принято в нашем мире, простота и эффективность алгоритмов зачастую лежат на разных чашах весов. Поэтому вычислительная сложность этого алгоритма выглядит вот так:
Худшее время: O(n2);
Среднее время: Θ(n2);
Лучшее время: Ω(n).
В статье про сложность алгоритмов мы использовали алгоритм сортировки пузырьком в качестве примера, поэтому подробно о том, почему сложность именно такая, можно посмотреть там.
Шейкерная сортировка
Шейкерная сортировка представляет собой двунаправленную пузырьковую сортировку. В этом случае алгоритм обрабатывает массив сначала слева направо, перемещая таким образом наибольший элемент в конец массива, а затем справа налево, перемещая наименьший элемент в начало массива. Ниже можно увидеть этот алгоритм реализованный на Java.
К сожалению, такой подход не позволяет уменьшить вычислительную сложность по сравнению с пузырьковой сортировкой и вычислительная сложность здесь такая же:
Худшее время: O(n2);
Среднее время: Θ(n2);
Лучшее время: Ω(n).
Сортировка расческой
Алгоритм сортировки расческой – это улучшение алгоритма сортировки пузырьком. Отличие здесь состоит в том, что сравниваются не соседние два элемента, а два элемента расположенные на определенном расстоянии друг от друга. Такой подход позволяет в начале сортировки переместить элементы с меньшими значениями из конца массива в начало, за счет этого и происходит уменьшение вычислительной сложности. Расстояние между сравниваемыми элементами выбирается не случайно, а с учетом фактора уменьшения. Оптимальным значением этого фактора принято брать число 1,247 которое вычисляется следующим образом
Таким образом, на первом проходе алгоритма расстояние между сравниваемыми элементами будет равно размеру массива поделенному на 1,247, и на каждом следующем шаге расстояние элементами будет делиться на эту величину.
Такой подход и правда позволяет снизить вычислительную сложность алгоритма, и здесь она будет такой:
Худшее время: O(n2);
Среднее время: Θ (n2/ 2p);
Лучшее время: Ω(n log n).
Но, нужно помнить, что эта сортировка является неустойчивой, т. е. она может менять относительный порядок одинаковых элементов.
На этом обзор простых сортировок подошел к концу. Дальше алгоритмы сортировки будут уже более сложными, но и более эффективными с точки зрения вычислительной сложности.
Узнать больше о других видах сортировок вы можете из материалов блога:
