Bubble sort in Python

In this article you can see  how to use Bubble sort in python .   Below you can find  two version of python code that sorts list using Buble sort method.

 

Step by step example:

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass

( 5 1 4 2 8 ) \to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass

( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass

( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )

Python Solution :

"""
1. Version
procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
          end if
       end for
       n = newn
    until n = 0
end procedure
"""
A=[5, 1, 4, 2, 8,0]
n=len(A)
swapped =True
iteration=0
while (swapped):
  swapped=False
  iteration+=1
  for i in range(1,n):
    iteration+=1
    if A[i-1] >A[i]:
      temp=A[i]
      A[i]=A[i-1]
      A[i-1]=temp
      swapped=True
print "1. Version solution: "+str(A)
print "Number of iterations: "+str(iteration)

#1. Version solution: [0, 1, 2, 4, 5, 8]
#Number of iterations: 36

 

"""
2. Version
procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure"""
A=[5, 1, 4, 2, 8,0] n=len(A)
iteration=0
swapped =True
while (swapped):
  iteration+=1
  swapped=False
  for i in range(1,n):
    iteration+=1
    if A[i-1] >A[i]:
      temp=A[i]
      A[i]=A[i-1]
      A[i-1]=temp
      swapped=True
  n=n-1
print "2.Version  solution: "+str(A)
print "Number of iterations: "+str(iteration)

#2.Version  solution: [0, 1, 2, 4, 5, 8]
#Number of iterations: 21

 

If you need better code overview you can find it on my github account  https://github.com/blaz1988/PythonCodility/blob/master/Bubble_sort.py

email@djangotutsme.com April 16, 2016, 9:36 a.m.