_edited_edited.png)
Hi There! This ‘Concept-into-Code’ blog post is the first in a series where I will try to explain concepts into code in the simplest ways that I can.
This is my first blog, trying to do simple and short about particular concepts that I’m learning about and share it with you.
Introduction to Bubble Sort
Bubble Sort is the simplest sorting algorithm. It is used to sort elements in Ascending order or Descending order. Its name resembles the way the Algorithm works: with every new pass, the largest element in the list “bubbles up” from the list.
Bubble sort consists of multiple passes through a list. During each pass, the algorithm compares adjacent elements and swap them if they are unsorted depending on their value and intended order.
Basically, Bubble sort performs three simple tasks:
Repeatedly going through the list of elements to sort.
Comparing adjacent elements with each other and sort them.
Swapping them around if they are not in the intended order.
Bubble Sort pseudocode
bubbleSort(inputArray)
n = length(inputArray)
for (1= 0 until n)
for (j = 0 until n-i-1)
if(array[j] > array[j + 1])
swap(array, j, j+1)
In this pseudocode, n is the length of our array. To ensure that our entire list is sorted we need to do n — 1 pass on our list. If we had a list of 10 items, we would need to compare the second element of our list (at position 1 in the array) and keep going through it 9 times until we have sorted the entire list. A sorted bubble is building at the end of the list, this is why we need to make n — 1 pass on our list.
In our, if statements, we are comparing the number in our array at position j with the number at position j + 1 (the adjacent number in our list).
To properly analyze how this algorithm works, here we are considering an Array of Strings [‘g’, ‘i’, ‘a’, ‘k’, ‘e’], we can also use an array of integers. Assume you’re using bubble_sort() from above. Here’s a figure illustrating what the array looks like at each iteration of the algorithm:
The above-unsorted list is not the worst case, the worst-case unsorted list would be a list in descending order. For such a list, that contains n elements, we need to perform (n-1) swaps for it to be sorted in ascending order. Observe how for the first round you need to sort all of the n elements, while on the second round you sort (n-1) elements and so on and so forth.
Implementing Bubble Sort in Python
Below is implementation to sort an Integer / String Array using Bubble sort in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
# sorting by using simultaneous assignment in python
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr1 = [7, 4, 3, 6, 2]
arr2 = ['g', 'i', 'a', 'k', 'e']
print('Before sorting an Integer Array: {}'.format(arr1))
bubble_sort(arr1)
print('After sorting an Integer Array: {}'.format(arr1))
print('Before sorting an String Array: {}'.format(arr2))
bubble_sort(arr2)
print('After sorting an String Array: {}'.format(arr2))
Output:
Before sorting an Integer Array: [7, 4, 3, 6, 2]
After sorting an Integer Array: [2, 3, 4, 6, 7]
Before sorting an String Array: ['g', 'i', 'a', 'k', 'e']
After sorting an String Array: ['a', 'e', 'g', 'i', 'k']Time Complexity
The time complexity of the Bubble Sort is O(n²).
Conclusion
This brings us to the end of the article where we learned about bubble Sort and its implementation in python
Hope this helps. Thanks