Python Program - Bubble Sort


Advertisements

Bubble sort is the simplest sorting algorithm. The Bubble sort is based on the idea that every adjacent elements are compared and swapped if found in wrong order.

Example:

To understand the bubble sort, lets consider an unsorted array $$[1, 23, 10, -2]$$ and discuss each step taken to sort the array in ascending order. In every pass, two adjacent elements are checked and swapped if found in wrong order.

First Pass: $$(1)$$ and $$(23)$$ are compared and found in correct order(ascending order in this case). After that $$(23)$$ and $$(10)$$ are compared, since $$(23>10)$$, hence these numbers are swapped. Then $$(23)$$ and $$(-2)$$ are compared and swapped.

Second Pass: $$(1)$$ and $$(10)$$ are compared and found in correct order. Then $$(10)$$ and $$(-2)$$ are compared, since $$(10>-2)$$, hence these numbers are swapped. After that $$(10)$$ and $$(23)$$ are compared and found in correct order.

Third Pass: $$(1)$$ and $$(-2)$$ are compared, since $$(1>-2)$$, hence these numbers are swapped. After that $$(1,10)$$ and $$(10,23)$$ are checked and found in correct order.

Bubble Sort

Implementation of Bubble Sort


# function for bubble sort
def bubblesort(MyList):
  for i in range(len(MyList)): 
    for j in range(len(MyList)-i-1):
      if(MyList[j]>MyList[j+1]):
        MyList[j] , MyList[j+1] = MyList[j+1], MyList[j]

# function to print list
def PrintList(MyList):
  for i in MyList:
    print(i, end=" ")
  print("\n")
  
# test bubble sort code                 
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
PrintList(MyList)

bubblesort(MyList)
print("Sorted List")
PrintList(MyList)

Output

Original List
1 10 23 50 4 9 -4 

Sorted List
-4 1 4 9 10 23 50 

Time Complexity:

The time complexity of bubble sort is $$\mathcal{O}(N^2)$$ in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.




Advertisements