Алгоритм сортировки массива методом пузырька python

Сортировка методом пузырька в 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, позволяющее не вводить дополнительную переменную для обмена значений двух и более переменных.

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

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

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

Заключение

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

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

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

Источник

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

Сортировка пузырьком – это простой алгоритм среди различных алгоритмов сортировки. Изучим его как первый алгоритм сортировки. Его легко освоить и он интуитивно очень понятен. Его несложно реализовать в коде, что очень выгодно для начинающих разработчиков программного обеспечения. Минус алгоритма в том, что для сортировки элементов данный метод производит проверку каждый раз, независимо от того, сортируется массив или нет.

Концепция пузырьковой сортировки

Пузырьковая сортировка в Python использует простую логику, которая работает, повторяя перемену местами соседних элементов , если они находятся в неправильном порядке. Она сравнивает одну пару и меняет местами, если первый элемент больше, чем второй; в противном случае переходит к следующей паре элементов для сравнения.

Мы создаем список элементов, в котором хранятся целые числа

Так алгоритм сортирует элементы:

Первая итерация

Он сравнивает первые два элемента, и здесь 5> 3, а затем меняет их местами. Теперь у нас есть новый список –

В третьем сравнении 8> 6, элементы меняются местами –

В четвертом сравнении 8> 7, элементы меняются местами –

В пятом сравнении 8> 2, также нужно их поменять местами –

На этом первая итерация завершена, и в конце мы получаем самый большой элемент. Теперь нам нужно len (list1) – 1

Вторая итерация

[3, 5, 6, 7, 2, 8] -> [3, 5, 6, 2, 7, 8] здесь 7> 2, происходит их перемена местами. Теперь

Третья итерация

Алгоритм будет повторяться, пока список не будет отсортирован.

Четвертая итерация

Пятая итерация

Мы видим, что наш список отсортирован с использованием метода пузырьковой сортировки.

Реализация в коде Python

Мы уже описывали технику пузырьковой сортировки. Теперь реализуем логику в коде Python.

# Creating a bubble sort function def bubble_sort(list1): # Outer loop for traverse the entire list for i in range(0,len(list1)-1): for j in range(len(list1)-1): if(list1[j]>list1[j+1]): temp = list1[j] list1[j] = list1[j+1] list1[j+1] = temp return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

В приведенном выше коде мы определили функцию bubble_sort(), которая принимает list1 в качестве аргумента.

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

Без использования временной переменной

Мы также можем поменять местами элементы, не используя временную переменную. У Python очень уникальный синтаксис. Мы можем использовать следующие строки кода.

def bubble_sort(list1): # Outer loop for traverse the entire list for i in range(0,len(list1)-1): for j in range(len(list1)-1): if(list1[j]>list1[j+1]): # here we are not using temp variable list1[j],list1[j+1] = list1[j+1], list1[j] return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

Оптимизация реализации кода Python

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

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

def bubble_sort(list1): # We can stop the iteration once the swap has done has_swapped = True while(has_swapped): has_swapped = False for i in range(len(list1) - 1): if list1[i] > list1[i+1]: # Swap list1[i], list1[i+1] = list1[i+1], list1[i] has_swapped = True return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort function print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The sorted list is: [2, 3, 5, 6, 7, 8]

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

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

На каждой последующей итерации мы можем сравнивать на один элемент меньше, чем раньше. Точнее, на k-й итерации нужно сравнить только первые n – k + 1 элементов:

def bubble_sort(list1): has_swapped = True total_iteration = 0 while(has_swapped): has_swapped = False for i in range(len(list1) - total_iteration - 1): if list1[i] > list1[i+1]: # Swap list1[i], list1[i+1] = list1[i+1], list1[i] has_swapped = True total_iteration += 1 print("The number of iteraton: ",total_iteration) return list1 list1 = [5, 3, 8, 6, 7, 2] print("The unsorted list is: ", list1) # Calling the bubble sort funtion print("The sorted list is: ", bubble_sort(list1))

The unsorted list is: [5, 3, 8, 6, 7, 2] The number of iteraton: 6 The sorted list is: [2, 3, 5, 6, 7, 8]

Сравнение времени

Давайте посмотрим на сравнение времени между приведенными выше фрагментами кода.

Unoptimized Bubble Sort Takes: 0.0106407 Optimize Bubble Sort Takes: 0.0078251 Bubble Sort with a Boolean flag and shortened list Takes: 0.0075207

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

Источник