Рубрики
Без рубрики

Понимание Python Bubble Sort с примерами

Python Bubble sort можно использовать везде, где требуется простота, но скорость медленная. В пузырьковой сортировке происходит обмен между соседними элементами

Автор оригинала: 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))
python bubble sort
ВЫХОД-
[3,5,6,7,9]

Пузырчатая сортировка python также работает со списком строк таким же образом.

list1=['bhavya','sonu','ashwini','zubair','dheeraj' ] 
print(bubble_sort(list1))
python bubble sort

При приведении приведенного выше списка функция возвращает вывод следующим образом:

['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))
python bubble sort
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. Простейший алгоритм сортировки.
  2. Поскольку сортировка занимает один и тот же список(обычно известный как сортировка на месте), она занимает меньше места. Пространство(1).
  3. Обычно используется для понимания основ сортировки.
  4. Если данные очень малы, они могут превзойти некоторые из лучших алгоритмов сортировки, таких как quicksort, поскольку они выполняют сложные вычисления над данными и занимают больше времени и пространства.

Ограничения сортировки пузырьков python

  1. Как мы уже отмечали выше, даже если список сортируется, алгоритм продолжает сортировать список до (n-1) – го прохода. Несмотря на то, что он имеет ту же временную сложность, что и вставка и другие методы сортировки, он работает медленнее.
  2. Из-за такого количества проходов и итераций это занимает много времени. Кроме того, поскольку в программе for loop используется внутри другого for loop, он имеет временную сложность O(n^2).

Вывод

Из всех методов сортировки python bubble sort является одним из самых простых методов сортировки и отлично подходит для начала работы, но не может быть использован для больших данных из-за его большой временной сложности.

Попробуйте запустить программы на вашей стороне и дайте мне знать, если у вас есть какие-либо вопросы.

Счастливого кодирования!