Введение в Bubble Sort в Python
Пузырьковая сортировка - это простой и логичный алгоритм сортировки. Принцип его работы основан на рекурсивной замене смежных элементов, если порядок неправильный. В этой теме мы собираемся узнать о Bubble Sort в Python.
Пузырьковая сортировка иногда также называется тонущей сортировкой, Ripple sort.
Давайте посмотрим это на примере:
Первый забег
( 6 1 4 3) -> ( 1 6 4 2): Здесь 1- й два элемента меняются местами, если порядок неправильный.
(1 6 4 2) -> (1 4 6 2): Здесь следующие два элемента меняются местами, если порядок неправильный.
(1 4 6 2 ) -> (1 4 2 6 ): здесь следующие два элемента меняются местами, если порядок неправильный.
Второй прогон
( 1 4 2 6) -> ( 1 4 2 6): Здесь сравниваются первые два элемента, но они не поменялись местами, так как порядок правильный.
(1 4 2 6) -> (1 2 4 6): Здесь следующие два элемента меняются местами, так как порядок был неправильным.
(1 2 4 6 ) -> (1 2 4 6 ): здесь последние два элемента сравниваются, но не меняются местами, поскольку порядок
Теперь мы знаем, что массив выглядит отсортированным, однако для того, чтобы узнать, выполнена ли сортировка, требуется один запуск без какой-либо подкачки.
Третий забег
( 1 2 4 6) -> ( 1 2 4 6): нет замены в двух первых элементах.
(1 2 4 6) -> (1 2 4 6): нет замены в следующих двух элементах.
(1 2 4 6 ) -> (1 2 4 6 ): в последних двух элементах нет свопов.
Поскольку на любом этапе не происходило перестановок, теперь алгоритм понимает, что сортировка идеальна.
Пузырьковая сортировка получила свое название, потому что элементы перемещаются в правильном порядке, который похож на пузырьки, поднимающиеся на поверхность.
Bubble sort на языке Python
Теперь давайте посмотрим на логическую реализацию пузырьковой сортировки через python. Python является очень широко используемым языком в наши дни. Понимание этого через python наверняка даст вам уверенность в том, что вы сможете писать на любом другом языке.
Код Python
def bubble_Sort(arr):
m = len(arr)
# Traverse through all the array elements
for u in range(m):
for v in range(0, mu-1):
# traverse the array from 0 to mu-1
# Swap if the element is greater than adjacent next one
if arr(v) > arr(v+1) :
arr(v), arr(v+1) = arr(v+1), arr(v)
Чтобы распечатать массив после пузырьковой сортировки, необходимо выполнить код:
for i in range(len(arr)):
print("%d" %arr(i)),
Here arr will be your array.
Объяснение кода Python
Здесь «m» - длина массива. Два цикла for содержат фактическую логику заземления, где «u» представляет первый элемент, а «v» представляет второй, с которым первый элемент должен сравниваться для замены, если порядок сортировки между ними не верен.
«Arr (v)> arr (v + 1)» это представляет сравнение последовательных элементов, если первый элемент больше, чем второй элемент, операция обмена будет выполняться следующим выражением:
То есть «arr (v), arr (v + 1) = arr (v + 1), arr (v)».
Эта операция обмена называется свопом. Хорошая часть - не требуется временная память для этого типа операции подкачки.
«U» представляет цикл каждого цикла, в то время как «v» представляет этапы каждого этапа. Пример в вышеупомянутом разделе может быть упомянут.
После выполнения пузырьковой сортировки можно увидеть отсортированный массив с кодом, указанным ниже:
for i in range(len(arr)):
print ("%d" %arr(i)),
Давайте посмотрим, как это ведет себя в Python IDE, для более глубокого понимания:
Выход:
Есть несколько фактов о Bubble Sort, которые каждый должен знать, прежде чем внедрять его:
- Пузырьковая сортировка часто считается плохим эффективным методом сортировки. Так как он должен обменивать предметы, пока не станет известно его окончательное местонахождение. Все это приводит к потерям операций и, следовательно, очень дорого. Этот алгоритм проходит через каждый элемент, где сортировка требуется или не требуется. Как только цикл проходит без какого-либо обмена, сортировка по пузырькам считается завершенной.
- Это самая простая из всех структур данных, для любого новичка это дает хорошую уверенность. Это легко построить и понять.
- Он использует много времени и памяти.
- Это считается стабильным алгоритмом, так как он сохраняет относительный порядок элементов.
- Считается хорошим для небольшого массива / списка. Тем не менее, это плохая идея использовать его для длинных.
Вывод
Проходя через вышеупомянутое содержание пузырьковой сортировки, можно было получить кристально четкое понимание этого алгоритма сортировки, специализирующегося на python. Как только вы освоитесь с логикой пузырьковой сортировки, вам будет легче понять другой набор структур данных. Логический подход - единственный способ добиться успеха в области структуры данных. Сначала нужно понять логику алгоритма структуры данных на каждом этапе, а затем нацелить его код на Python или на любом другом языке.
Рекомендуемые статьи
Это руководство по Bubble Sort в Python. Здесь мы рассмотрим логическую реализацию пузырьковой сортировки через код Python с объяснением. Вы также можете посмотреть следующую статью, чтобы узнать больше -
- Петли в Python
- Файловые операции Python
- Палиндром в Python
- 3D-массивы в Python
- Особенности Python
- Обмен в PHP
- 3D-массивы в C ++
- Палиндром в C ++
- Палиндром в JavaScript
- Как работают массивы и списки в Python?