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.

First Pair (adjacent elements)
Second Pair (adjacent elements)
Third Pair (adjacent elements)

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

Lets take an overview – Bubble Sort Algorithm

Bubble Sort Algorithm

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.

Bubble sort advantages

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.

Bubble sort Disadvantages

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

  • It does not perform well when sorting large lists. It takes too much time and resources.
  • It’s mostly used for academic purposes and not the real-world application.
  • The number of steps required to sort the list is of the order n2

Leave a Reply

Your email address will not be published. Required fields are marked *