# Bubble Sort Program in Python Bubble sort is a sorting algorithm that uses the swapping of elements to sort the list in either ascending or descending order. Bubble sort is the simplest and easy-to-understand sorting algorithm. In this article, we will learn more about bubble sort, the bubble sort algorithm in python, and the time and space complexity of the bubble sort program in python.

## What is Bubble Sort Python?

The bubble sort algorithm compares adjacent elements and swaps them to sort the list. The bubble sort uses two for loops to sort the list. The first for loop (outer for loop) is used to traverse the list n times. The Second for loop (inner for loop) is used to traverse the list and swap elements if necessary.

## Bubble Sort Algorithm Python:-

Let’s understand how the bubble sort algorithm python works using an example and visualizing the algorithm. The process of sorting the list in ascending using the bubble sort algorithm python is given below. Now Let’s see how n-1 (n=size of a list) list passes work on a list.

First pass (i=0) • First, we will run the inner loop for n-i-1 (5-0-1 = 4) times and we will compare each adjacent pair.
• For j=0, compare j=0 (l=4) and j+1=1 (l=3) here l[j]>l[j+1] so we will swap two elements because we want higher elements on the right side to sort a list.
• For j=1, l (4) < l (9) so we will not swap elements because the higher element (9) is already on the right side.
• For j=2, l (9) > l (1) so we will swap elements.
• For j=3, l (9) > l (5) so we will swap elements.
• After performing the first pass we can see that the last element of a list (9) is already at its right position so in further passes we will not touch that element.

Second pass (i=1) • In the second pass (i=1), we will run inner loop n-i-1 time ( 5-1-1 =3) which one less than the first pass it is because the last element is already sorted in the second pass so we will not consider the last element.
• For j=0, l (3) < l (4) so we will not swap elements.
• For j=1, l (4) > l (1) so we will swap elements.
• For j=2, l (4) < l (5) so we will not swap elements
• After the completion of the second pass, we can see that the last two elements of an list ( [5,9] ) are in their right position.

Third pass (i=2) • In the third pass ( i=2 ), we will run the inner loop n-i-1 (5-2-1 = 2) times.
• For j=0, l (3) > l (1) so we will swap elements.
• For j=1, l (3) < l (4) so we will not swap elements.
• After performing the third pass we can see that the last three elements ( [4,5,9] ) are in their right positions.

Fourth pass (i=3) • In the fourth pass (i=3 ), we will run the inner loop n-i-1 (5-3-1=1) times.
• For j=0, l (1) < l (3) so we will not swap elements.
• After performing the fourth pass we can see that our list is sorted.

Sorting happens in place in bubble sort python which means if there are two elements with the same values so after performing the bubble sort program in python the order of that two elements will be the same. Let’s understand this with an example list= [4,6,3,6,5] here two same elements are 6 at index 2 and 4 now after performing bubble sort list= [3,4,5,6,6] now two elements which is same are 6 at index 4 and 5 so element 6 at index 4 is element 6 at index 2 before performing sorting and element 6 at index 5 is the element at index 4 before performing sorting.

## Bubble Sort Program in Python:-

```def bubble_sort(list1):
for i in range(0,len(list1)-1):
for j in range(len(list1)-1):
if(list1[j]>list1[j+1]):
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp
return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
print("The sorted list is: ", bubble_sort(list1))```

Output

``````The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]``````

There is one problem with the above bubble sort program in python when a given list is already sorted the above program will still finish all the two loops so the time complexity becomes O(n^2) though the list is already sorted. Let’s see how can we optimize the above bubble sort program in python.

### Optimized Bubble Sort Program in Python:-

We can observe one thing if our list is already sorted then no swap will be performed so we can use this observation to write an optimized bubble sort program in python.

```def bubble_sort(list1):
has_swapped = True

while(has_swapped):
has_swapped = False
for i in range(len(list1) - 1):
if list1[i] > list1[i+1]:
# Swap
list1[i], list1[i+1] = list1[i+1], list1[i]
has_swapped = True
return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
print("The sorted list is: ", bubble_sort(list1))```

## Time Complexity Analysis of Bubble Sort Python

Best:- O(n) when the given list is already sorted at that time program using only one loop.
Average:- O(n^2) when the given list is not sorted.
Worst:- O(n^2) when the given list is reverse sorted at that time we have to perform a swap for each comparison. So the total swaps performed will be n*(n-1)/2

## Auxiliary Space complexity of bubble sort python

Auxiliary space complexity:- O(1) it’s because we are not using any extra list to perform bubble sort python. We are only using variables so the space complexity is O(1) to perform the bubble sort algorithm python.