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
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.
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
The values 21 and 33 are compared to find the greater one.
The value 33 is greater than 21, so no swapping takes place.
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
The new list after the second iteration is as follows
The new list after the third iteration is as follows
The new list after the fourth iteration is as follows
Lets take an overview – Bubble Sort Algorithm
Python Code for Bubble Sort
An optimized version of Bubble Sort
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]
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
- Defines a function bubbleSort that accepts a parameter theSeq. The code does not output anything.
- Gets the length of the array and assigns the value to a variable n. The code does not output anything
- Starts a for loop that runs the bubble sort algorithm (n – 1) times. This is the outer loop. The code does not output anything
- 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
- 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.
- 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.
- Assigns the value of theSeq[j] to a temporal variable tmp if the condition evaluates to true. The code does not output anything
- The value of theSeq[j + 1] is assigned to the position of theSeq[j]. The code does not output anything
- The value of the variable tmp is assigned to position theSeq[j + 1]. The code does not output anything
- The flag variable is assigned the value 1 to indicate that a swap has taken place. The code does not output anything
- Uses an if statement to check if the value of the variable flag is 0. The code does not output anything
- If the value is 0, then we call the break statement that steps out of the inner loop.
- Returns the value of theSeq after it has been sorted. The code outputs the sorted list.
- Defines a variable el that contains a list of random numbers. The code does not output anything.
- Assigns the value of the function bubbleSort to a variable result.
- 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