# Python Program - Bubble Sort

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.

## 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 the code
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
PrintList(MyList)

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

The above code will give the following 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 Θ(N²) 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.

5