Python Program for Bubble Sort

What is Bubble Sort?

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

It compares one pair at a time and swaps if the elements are not in order; otherwise, move further to the next pair of elements for comparison. This process is repeated until all the values in a list have been compared and swapped if necessary.

Each iteration is usually called a pass. The number of passes in a bubble sort is equal to the number of elements in a list minus one.

But it is one of the worst algorithm for sorting because it checks every time the array is sorted or not.

Bubble Sort Algorithm

Given a list of five elements, the following images illustrate how the bubble sort iterates through the values when sorting them

The following image shows the unsorted list

First Iteration

Step 1)

The values 21 and 6 are compared to check which one is greater than the other.

21 is greater than 6, so 21 takes the position occupied by 6 while 6 takes the position that was occupied by 21

Our modified list now looks like the one above.

Step 2)

The values 21 and 9 are compared.

21 is greater than 9, so we swap the positions of 21 and 9

The new list is now as above

Step 3)

The values 21 and 33 are compared to find the greater one.

The value 33 is greater than 21, so no swapping takes place.

Step 4)

The values 33 and 3 are compared to find the greater one.

The value 33 is greater than 3, so we swap their positions.

The sorted list at the end of the first iteration is like the one above

Second Iteration

The new list after the second iteration is as follows

Third Iteration

The new list after the third iteration is as follows

Fourth Iteration

The new list after the fourth iteration is as follows

Python Code for Bubble Sort

An optimized version of Bubble Sort

def bubbleSort(arr):
n = len(arr)

```# Traverse through all array elements
for i in range(n):
swapped = False

# Last i elements are already
# in place
for j in range(0, n-i-1):

# traverse the array from 0 to
# n-i-1. Swap if the element
# found is greater than the
# next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True

# IF no two elements were swapped
# by inner loop, then break
if swapped == False:
break```

Driver code to test above

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print (“Sorted array :”)
for i in range(len(arr)):
print (“%d” %arr[i],end=” “)

Code Explanation for Bubble Sort

The explanation for the code is as follows

HERE,

1. Defines a function bubbleSort that accepts a parameter theSeq. The code does not output anything.
2. Gets the length of the array and assigns the value to a variable n. The code does not output anything
3. Starts a for loop that runs the bubble sort algorithm (n – 1) times. This is the outer loop. The code does not output anything
4. Defines a flag variable that will be used to determine if a swap has occurred or not. This is for optimization purposes. The code does not output anything
5. Starts the inner loop that compares all the values in the list from the first to the last one. The code does not output anything.
6. Uses the if statement to check if the value on the left-hand side is greater than the one on the immediate right side. The code does not output anything.
7. Assigns the value of theSeq[j] to a temporal variable tmp if the condition evaluates to true. The code does not output anything
8. The value of theSeq[j + 1] is assigned to the position of theSeq[j]. The code does not output anything
9. The value of the variable tmp is assigned to position theSeq[j + 1]. The code does not output anything
10. The flag variable is assigned the value 1 to indicate that a swap has taken place. The code does not output anything
11. Uses an if statement to check if the value of the variable flag is 0. The code does not output anything
12. If the value is 0, then we call the break statement that steps out of the inner loop.
13. Returns the value of theSeq after it has been sorted. The code outputs the sorted list.
14. Defines a variable el that contains a list of random numbers. The code does not output anything.
15. Assigns the value of the function bubbleSort to a variable result.
16. Prints the value of the variable result.

The following are some of the advantages of the bubble sort algorithm

• It is easy to understand
• It performs very well when the list is already or almost sorted
• It does not require extensive memory.
• It is easy to write the code for the algorithm
• The space requirements are minimal compared to other sorting algorithms.