Bubble Sort in Python
The basic idea behind bubble sort is to compare the first element in list to second element .
Compare the second element to the third element if greater swap the elements.
Compare the third element to the fourth element if greater swap the elements.
Do until the list is sorted.
The Python code for bubble sort.
import numpy as np
a=[10,5,-1,6,7,15,20,16,15,18]
for i in np.arange(10):
for j in np.arange(10-i-1):
if a[j] > a[j+1]:
s=a[j]
a[j]=a[j+1]
a[j+1]=s
print(a)
Output of the program would be
[-1, 5, 6, 7, 10, 15, 15, 16, 18, 20]
Explanation of Program
The statement “import numpy as np” imports numpy module and rename as np.
The statement a=[10,5,-1,6,7,15,20,16,15,18] initialize a list a.
The statement “for i in np.arange(10):” is for passes in bubble sort.
The statement “for j in np.arange(10-i-1):” is for number of comparisons.
The statement “if a[j] > a[j+1]:” compares the adjacent elements in list.
The statements “s=a[j] a[j]=a[j+1] a[j+1]=s” swaps the value of a[j] to a[j+1] if the above statement is true.
The statement “print(a)” prints the sorted list.
Time Complexity of the Bubble Sort Algorithm
If there are n elements in a list then.
The first pass will require (n-1) comparisons.
The the second pass will require (n-2) comparisons.
The third pass will require (n-3) comparisons.
. . . . . . .
. . . . . . .
. . . . . . .
The last pass will require only one pass.
Then the total number of comparisons
=(n-1)+(n-2)+(n-3)+ (n-4)+…………..+1= n(n-1)/2= O(n2)
Then the complexity of bubble sort is O(n2).
Conclusion
Before making bubble sort in Python program you must have made in C/C++ or in Java. However, it is easy way to learn a programming language, to make the same programs what you have built in other languages.