Сорта пузырьков является самым простым алгоритмом сортировки, сравнивает смежное значение и обменивается элементом на основе условия. В сортировке восходящего порядка в основном то, что он делает, сравнивает два значения и изменяет положение, перечитывает ее через значения и поместите самое высокое значение в конце.
Для этого примера мы принимаем это значение в качестве ввода значений -> [6, 5, 3, 1, 8, 7]
Отслеживание
ЭТАП 1
Input [6, 5, 3, 1, 8, 7] compare position 0 and 1 values ---> 6>5 position 0 is greate than 1, swap it [5, 6, 3, 1, 8, 7] compare position 1 and 2 values ---> 6>3 position 1 is greate than 2, swap it [5, 3, 6, 1, 8, 7] compare position 2 and 3 values --------> 6>1 position 2 is greate than 3, swap it [5, 3, 1, 6, 8, 7] compare position 3 and 4 values --------> 6>8 position 3 is less than 4, no swap [5, 3, 1, 6, 8, 7] compare position 4 and 5 values --------> 8>7 position 4 is greate than 5, swap it [5, 3, 1, 6, 7, 8]
Значение последнего позиции 8 заблокировано
Этап 2
Input [5, 3, 1, 6, 7] compare position 0 and 1 values --------> 5>3 position 0 is greate than 1, swap it [3, 5, 1, 6, 7] compare position 1 and 2 values --------> 5>1 position 1 is greate than 2, swap it [3, 1, 5, 6, 7] compare position 2 and 3 values --------> 5>6 position 2 is less than 3, no swap [3, 1, 5, 6, 7] compare position 3 and 4 values --------> 6>7 position 3 is less than 4, no swap [3, 1, 5, 6, 7]
Значение последнего позиции 7 заблокировано
Этап 3
Input [3, 1, 5, 6] compare position 0 and 1 values --------> 3>5 position 0 is less than 1, no swap [3, 5, 1, 6] compare position 1 and 2 values --------> 5>1 position 1 is greate than 2, swap it [3, 1, 5, 6] compare position 2 and 3 values --------> 5>6 position 2 is less than 3, no swap [3, 1, 5, 6]
Значение последнего позиции 6 заблокировано
Этап 4
Input [3, 1, 5] compare position 0 and 1 values --------> 3>1 position 0 is greate than 1, swap it [1, 3, 5] compare position 1 and 2 values --------> 3>1 position 1 is less than 2, no swap [1, 3, 5]
Значение последнего позиции 5 заблокировано
Этап 5
Input [1, 3] compare position 0 and 1 values --------> 3>1 position 0 is less than 1, no swap [1, 3]
Значение последнего позиции 3 заблокировано
Сортированный результат 1, 3, 5, 6, 7, 8
def bubbleSort(k):
last = 0
for i in range(0,len(k)):
# reduce the last value to avoid over lapping
for j in range(0,len(k)-1-last):
# compare the adjustent value
if k[j] > k[j+1]:
k[j], k[j+1] = k[j+1], k[j]
last+=1
print(k)
return k
k = [3,40,2,0,10]
bubbleSort(k)
"""
result
[3, 2, 0, 10, 40]
[2, 0, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]
"""
Другой метод
Если значения уже отсортированы или в середине процесса, если они отсортируются, вам не нужно делать процесс до конца. Мы можем остановить это, когда значения будут отсортированы.
def bubbleSort(k):
last = 0
for i in range(0,len(k)):
# when the list is already sorted, its better to stop this will increase the process time
done = True
# reduce the last value to avoid over lapping
for j in range(0,len(k)-1-last):
# compare the adjustent value
if k[j] > k[j+1]:
k[j], k[j+1] = k[j+1], k[j]
done = False
if done:
break
last+=1
print(k)
return k
k = [3,40,2,0,10]
bubbleSort(k)
"""
result
[3, 2, 0, 10, 40]
[2, 0, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]
"""
Вы можете увидеть разницу в результате первого метода, запускающегося до конца, во втором методе, как только список сортируется, он остановится.
Временные сложности
Bubble Sort имеет наихудшую и среднюю сложность O (N2), лучший случай O (n), если значения уже отсортированы.
Оригинал: “https://dev.to/magesh236/bubble-sort-in-python-4l2a”