Imagine that we have a list of numbers we wish to sort in ascending or descending order. For this, we need a sorting algorithm that puts an elements of an array in a certain order. Of many sorting algorithm, bubble sort algorithm is one of the simplest. Though it performs poorly in the real world is often used in educational purpose because of its simplicity.
Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. It makes multiple passes through a list. Each pass through the list places the next largest value in its proper place.
The “Bubble” sort is called so because the list elements with greater value than their surrounding elements “bubble” towards the end of the list. For example, after first pass, the largest element is bubbled towards the rightmost position. After second pass, the second largest element is bubbled towards the second last position in the list and so on.
How does it works?
Let’s say we have an array of length n. Bubble sort compares all the element one by one and sort them based on their values.
- The first and second elements in the list are compared and swapped by the sorting program in case they are in the wrong order.
- Then second and third elements in the list are compared and swapped by the sorting program in case they are in the wrong order.
- This process continues until the last element present in the list is compared and swapped in the same fashion.
- All the steps are iterated until the entire list gets sorted.
Pseudocode of Bubble Sort Algorithm
Pseudo-code of Bubble Sort algorithm is as follows:
begin BubbleSort(list)
for i in range(n-1):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
end if
end for
end for
return list
end BubbleSort
Bubble Sort Example
Consider the following array:
First Iteration
We proceed with the first and second element i.e., index[0] and index[1]. Check if 5 > 3 which is True. So, we swap index[0] and index[1] the array remains the same.
Swap index[0] and index[1].
Now proceed with the second and third element i.e., index[1] and index[2]. Check if 5 > 6 which is false, no swapping happens and the array remains the same.
We proceed with the third and fourth element i.e., index[2] and index[3]. Check if 6 > 1 which is true.
Swap index[2] and index[3].
We proceed with the fourth and fifth element i.e., index[3] and index[4]. Check if 6 > 4 which is true.
Swap index[3] and index[4],
This is the end of the first iteration, where the Largest element reaches its final(last) position.
Second Iteration
Proceed with the first and second element i.e., index[0] and index[1]. Check if 3 > 5 which is false.
So, no swapping happens and the array remains the same.
We now proceed with the second and third element i.e., index[1] and index[2]. Check if 5 > 1 which is true.
So, we swap index[1] and index[2].
We now proceed with the third and fourth element i.e., index[2] and index[3]. Check if 5 > 4 which is true.
So, we swap index[2] and index[3].
After the third iteration, the third largest element will be at the third last position in the array. And after the nth iteration, the nth largest element(smallest element) will be at nth last position(1st position) in the array, where ‘n’ is the size of the array.
After doing all the iteration, we can easily see the array will be sorted.
Thus, the sorted array will look like this:
Code for Bubble Sort Algorithm in Python
# Bubble sort algorithm in Python
def BubbleSort(arr):
# Outer loop for traverse the entire list
n = len(arr)
for i in range(n-1) :
flag = 0
# range(n) also work but outer loop will repeat one time more than needed.
# traverse the array from 0 to n-i-1
for j in range(0, n-i-1) :
#Swap if the element found is greater than the next element
if arr[j] > arr[j+1]:
arr[j+1], arr[j] = arr[j], arr[j+1]
flag = 1
if flag ==0:
break
return arr
arr = [5, 3, 6, 1, 4]
print("Unsorted list: ", arr )
# Calling the bubble sort function
print("Sorted List: ", BubbleSort(arr))
#Output
Unsorted list: [5, 3, 6, 1, 4]
Sorted List: [1, 3, 4, 5, 6]
In the above bubble sort algorithm in Python, we have defined :
- A BubbleSort() function which takes arr as an argument. The code does not output anything.
- Assigned the length of the array in n.
- Inside the function, we have defined two for loop.
- First for loop is outer loop that runs the bubble sort algorithm (n – 1) times.
- Defines a flag variable that will be used to determine if a swap has occurred or not. This is for optimization purposes.
- Then starts the inner for loop that compares all the values in the list from the first to the last one.
- Define the condition in the inner for loop; if first index value is greater than the second index value, swap their positions with each other.
- The flag variable is assigned the value 1 to indicate that a swap has taken place. Uses an if statement to check if the value of the variable flag is 0.
- If the value is 0, then we call the break statement that steps out of the inner loop
- Call the function and passed arr; it iterated and returned the sorted arr.
You may also like
Bubble Sort Advantages
- It is easy to understand.
- It does not require extensive memory.
- Easy to write the code for the algorithm.
- Elements are swapped in place without using additional temporary storage, space requirement is minimum.
- Performs greatly when array is almost sorted.
Complexity Analysis of Bubble Sort Algorithm
Sort complexity
The sort complexity is used to express the amount of execution times and space that it takes to sort the list. The bubble sort makes (n – 1) iterations to sort the list where n is the total number of elements in the list.
Time complexity
The time complexity of the bubble sort is O(n)
The time complexities can be categorized as:
- Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as [Big-O] O(n2)
- Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as [Big-Omega] Ω(n)
- Average case – this occurs when the list is in random order. The average Complexity is represented as [Big-theta] ⊝(n2)
Space complexity
The space complexity measures the amount of extra space that is needed for sorting the list. The bubble sort only requires one (1) extra space for the temporal variable used for swapping values. Therefore, it has a space complexity of O (1).
Conclusion
Sorting algorithm are most important concepts for every programmer. Implementing bubble sort algorithm in python is relatively straightforward. All you need is for loops and if statements.
C P Gupta is a YouTuber and Blogger. He is expert in Microsoft Word, Excel and PowerPoint. His YouTube channel @pickupbrain is very popular and has crossed 9.9 Million Views.