Сортировка пузырьком.

Данный вид сортировки является первым в нашем списке алгоритмов. И, при этом, самым простым и, наверное, вообще никогда не используемым. Вы спросите: зачем его тогда вообще изучать? Ответ кроется в его абсолютной простоте. Прежде, чем двигаться дальше, стоит попробовать свои силы в реализации самого простого из алгоритмов, чтобы понять, что собственно к чему.

Алгоритм заключается в следующем: берем первый элемент сортируемой последовательности и сравниваем его со следующим элементом. Если второй элемент больше, то меняем их местами. Теперь сдвигаемся на один шаг вправо и повторяем тоже самое. Делаем это до конца последовательности. В этом случае в самой правой крайней позиции окажется самый большой элемент. Теперь точно также сортируем остальные с учетом того, что сортируемая последовательность стала меньше на единицу. Данный метод сортировки как раз и получил свое название из-за того, что элемент в ходе перестановок как бы всплывает наверх.

Теперь давайте реализуем его на практике.

Метод принимает на вход целочисленный массив, подлежащий сортировке. Далее в цикле мы начинаем выполнять саму сортировку. Здесь используется две переменные begin и end. Переменная begin соответствует текущему элементу, выбранному для сортировки, а end означает текущую длину неотсортированной части массива. Сортировка завершится тогда, когда длина неотсортированной части массива станет равна нулю. В алгоритме также используется вспомогательный метод swap(), который выполняет перестановку двух элементов местами в случае необходимости. Реализация данного метода приведена ниже.

Вы можете проверить выполнимость данного алгоритма на практике. Что касается быстродействия, то об этом мы упомянули в начале статьи. Алгоритм на каждом проходе выполняет n-1, n-2, n-3 и т.д. сравнений, т.е. приблизительно n2/2 сравнений. Кроме того выполняется приблизительно n2/4 перестановок, а общая временная сложность оценивается в O(N2).

Реализация на языке С:

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

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *