Автор оригинала: Team Python Pool.
Понимание Python Bubble Sort с примерами
Сортировка-это метод упорядочивания данных в любой конкретной форме, например, в порядке возрастания или убывания. У нас есть много методов сортировки данных, но пузырьковая сортировка в python-одна из самых простых. В Python Bubble Sort замена происходит между соседними элементами (элементами, которые находятся непосредственно слева или справа), если они находятся не в правильном порядке.
Python Bubble sort можно использовать везде, где требуется простота, но скорость может быть скомпрометирована. Он использует очень мало места по сравнению с другими методами сортировки.
Концепция, используемая в пузырьковой сортировке
Концепция, используемая для сортировки пузырьков, объясняется ниже на примере.
Предположим, у нас есть список из 5 элементов “список 1”, и мы хотим отсортировать список в порядке возрастания( от наименьшего к наибольшему).
list1=[7,5,9,6,3]
ПАСС-1
7 5 9 6 3 -> 5 7 9 6 3 (swapped because 7>5) 5 7 9 6 3 -> 5 7 9 6 3 (not swapped because 7<9) 5 7 9 6 3 -> 5 7 6 9 3 (swapped because 9>6) 5 7 6 9 3 -> 5 7 6 3 9 (swapped because 9>3)
Мы нашли самый большой элемент “9”, и он не будет участвовать в дальнейших итерациях( мы можем сказать 9′ )
ПАСС-2
5 7 6 3 9 -> 5 7 6 3 9 (not swapped because 5<7) 5 7 6 3 9 -> 5 6 7 3 9 (swapped because 7>6) 5 6 7 3 9 -> 5 6 3 7 9 (swapped because 3>7)
Мы нашли второй по величине элемент “7”, и он также будет исправлен.
ПАСС-3
5 6 3 7 9 -> 5 6 3 7 9 (not swapped because 5<7) 5 6 3 7 9 -> 5 3 6 7 9 (swapped because 6>3)
Мы нашли третий по величине элемент “6”, и он также будет исправлен.
ПАСС-4
5 3 6 7 9 -> 3 5 6 7 9 (swapped because 5<3)
Наконец – то мы получили сортированный список.
Наблюдения
Мы успешно применили пузырьковую сортировку в списке 1, и из нее можно сделать следующие наблюдения.
- Общее количество проходов равно 4 для списка из 5 элементов. Таким образом, можно сделать вывод, что для сортировки списка с помощью пузырьковой сортировки требуется n-1 проходов .
- Количество итераций за проход уменьшается на 1. Для Pass-1 у нас есть 4 итерации. Для Pass-2 у нас есть 3 итерации, и это продолжается до 1 href=”https://en.wikipedia.org/wiki/Iteration”>итерация остается. Следовательно, число итераций- n-1, n-2, — n/n. href=”https://en.wikipedia.org/wiki/Iteration”>итерация остается. Следовательно, число итераций- n-1, n-2, — n/n.
Реализация пузырьковой сортировки в python:
Для сортировки в порядке возрастания:
# Python Bubble Sort program
def bubble_sort(list1):
for i in range(0,len(list1)-1): # The total number of passes,bubbles: i
for j in range(0,len(list1)-i-1): # The total number of iterations: j
if list1[j] > list1[j+1]:
[j+1],list1[j] # swap elements
return list1
list1=[7, 5, 9, 6, 3]
print(bubble_sort(list1))ВЫХОД-
[3,5,6,7,9]
Пузырчатая сортировка python также работает со списком строк таким же образом.
list1=['bhavya','sonu','ashwini','zubair','dheeraj' ] print(bubble_sort(list1))
При приведении приведенного выше списка функция возвращает вывод следующим образом:
['ashwini', 'bhavya', 'dheeraj', 'sonu', 'zubair']
Для сортировки в порядке убывания-
def bubble_sort_descending(list1):
for i in range(0,len(list1)-1):
for j in range(0,len(list1)-i-1):
if list1[j] < list1[j+1]:# Observe '<' is used instead of '>'
[j+1],list1[j]
return list1
list1=[7, 5, 9, 6, 3]
print(bubble_sort_descending (list1))OUTPUT- [9, 7, 6, 5, 3]
Pass- 1 [7, 5, 9, 6, 3] [7, 5, 9, 6, 3] [7, 9, 5, 6, 3] [7, 9, 6, 5, 3] Pass- 2 [7, 9, 6, 5, 3] [9, 7, 6, 5, 3] [9, 7, 6, 5, 3] Pass- 3 [9, 7, 6, 5, 3] [9, 7, 6, 5, 3] Pass- 4 [9, 7, 6, 5, 3]
Мы можем наблюдать, что получили правильный вывод 2-й проход итерации-2, но все же наш алгоритм продолжает сортировать уже отсортированный список. Это один из недостатков пузырьковой сортировки. Эта проблема может быть решена с помощью вставки или любого другого алгоритма сортировки. Для лучшего понимания Inserting sort посетите сайт http://pythonpool.com/insertion-sort-python/
Вставка Сортировка Углубленное Учебное видео
Преимущества пузырьковой сортировки
- Простейший алгоритм сортировки.
- Поскольку сортировка занимает один и тот же список(обычно известный как сортировка на месте), она занимает меньше места. Пространство(1).
- Обычно используется для понимания основ сортировки.
- Если данные очень малы, они могут превзойти некоторые из лучших алгоритмов сортировки, таких как quicksort, поскольку они выполняют сложные вычисления над данными и занимают больше времени и пространства.
Ограничения сортировки пузырьков python
- Как мы уже отмечали выше, даже если список сортируется, алгоритм продолжает сортировать список до (n-1) – го прохода. Несмотря на то, что он имеет ту же временную сложность, что и вставка и другие методы сортировки, он работает медленнее.
- Из-за такого количества проходов и итераций это занимает много времени. Кроме того, поскольку в программе for loop используется внутри другого for loop, он имеет временную сложность O(n^2).
Вывод
Из всех методов сортировки python bubble sort является одним из самых простых методов сортировки и отлично подходит для начала работы, но не может быть использован для больших данных из-за его большой временной сложности.
Попробуйте запустить программы на вашей стороне и дайте мне знать, если у вас есть какие-либо вопросы.
Счастливого кодирования!