Сортировка методом пузырька в Python

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

Сортировка пузырьком — это один из самых простых, но и малоэффективных алгоритмов, который используется для сортировки небольших массивов.

Алгоритмы сортировки на собеседовании

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

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

Кроме того, в Python и других языках программирования существуют встроенные функции, которые производят сортировку быстро и эффективно.

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

  • Уметь классифицировать алгоритмы сортировки.
  • Знать преимущества и недостатки популярных алгоритмов, чтобы понимать, когда каждый из них лучше использовать.
  • Понимать, что такое сложность алгоритма и как с её помощью определять, подходит ли он для решения данной задачи.

Метод пузырька

Сортировка пузырьком в основном применяется в учебных проектах. В реальной практике её заменяют более эффективные алгоритмы, однако сортировка пузырьком лежит в основе некоторых из них.

В общем случае алгоритм сортировки пузырьком следующий:

  1. Сравнить текущий элемент со следующим.
  2. Если следующий элемент меньше/больше текущего, поменять их местами.
  3. Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.

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

Внешний цикл в худшем случае совершает N (кол-во элементов) – 1 проходов, то есть внутренний цикл выполняется N-1 раз.

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

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

Сложность алгоритма

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

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

Алгоритм сортировки пузырьком имеет сложность O(n²), где n – количество элементов массива. Из формулы видно, что сложность сортировки пузырьком квадратично зависит от количества сортируемых элементов. Это значит, что он неэффективен при работе с большими массивами данных.

Следует понимать, что с помощью асимптотической функции нельзя точно вычислить время работы алгоритма. Например, дана последовательность “6 5 4 3 2 1”, для её сортировки придется сделать максимальное количество проходов. Такой случай называют наихудшим. Если дана последовательность “3 1 2 4 5”, то количество проходов будет минимально, соответственно сортировка пройдет гораздо быстрее. Если же дан уже отсортированный массив, то алгоритму сортировки и вовсе не нужно совершать проходов. Это называется наилучшим случаем.

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

Сортировку пузырьком лучше вывести в отдельную функцию. Код функции будет выглядеть так:

def bSort(array):
    # определяем длину массива
    length = len(array)
    #Внешний цикл, количество проходов N-1
    for i in range(length):
        # Внутренний цикл, N-i-1 проходов
        for j in range(0, length-i-1):
            #Меняем элементы местами
            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] = temp

Реализовать обмен значений соседних элементов можно в одну строку, использовав множественное присваивание, тогда код будет выглядеть так:

array[j], array[j+1] = array[j+1], array[j]

Множественное присваивание — одна из полезных фич Python, позволяющее не вводить дополнительную переменную для обмена значений двух и более переменных.

Чтобы продемонстрировать работу функции пузырьковой сортировки, создадим список, которые необходимо отсортировать:

a = [3, 1, 6, 4]

Отсортируем его с помощью нашей функции и выведем на экран:

bSort(a)
print(a) # Выведет [1, 3, 4, 6]

Заключение

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

На самом деле, вместо самостоятельного написания алгоритмов сортировки программисты на Python используют стандартные функции и методы языка, такие как sorted() и sort(). Эти функции отлажены и работают быстро и эффективно.

Знания особенностей алгоритмов сортировки, их сложности и принципов реализации в общем виде пригодятся каждому программисту, желающему пройти собеседование и стать Python-разработчиком.