## 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 ) ( **1** **5** 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 **5** **4** 2 8 ) ( 1 **4** **5** 2 8 ), Swap since 5 > 4

( 1 4 **5** **2** 8 ) ( 1 4 **2** **5** 8 ), Swap since 5 > 2

( 1 4 2 **5** **8** ) ( 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 ) ( **1** **4** 2 5 8 )

( 1 **4** **2** 5 8 ) ( 1 **2** **4** 5 8 ), Swap since 4 > 2

( 1 2 **4** **5** 8 ) ( 1 2 **4** **5** 8 )

( 1 2 4 **5** **8** ) ( 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 ) ( **1** **2** 4 5 8 )

( 1 **2** **4** 5 8 ) ( 1 **2** **4** 5 8 )

( 1 2 **4** **5** 8 ) ( 1 2 **4** **5** 8 )

( 1 2 4 **5** **8** ) ( 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)

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