Introduction
In this article, we will delve into two basic sorting algorithms: Bubble Sort and Insertion Sort. We will explore their steps, implementation in Python code, time complexity, advantages, and disadvantages, providing you with a comprehensive understanding of these fundamental sorting techniques.
Whether you're a beginner in computer science or a seasoned programmer, this comparison will sharpen your knowledge and help you make informed decisions when choosing the right sorting algorithm for your projects.
Bubble Sort
Bubble sort works by comparing two values at a time and sorting those two values as it iterates through the entire list.
You can think of it as if it's creating a bubble of the list every time it compares two consecutive values.
The bubble sort algorithm passes through the list n - 1 times and iterates through 1 less element each iteration.
Just from the description, you may already tell that the bubble sort algorithm is not an efficient sorting algorithm.
However, bubble sort is a good algorithm for beginner software engineers to study and understand so that they grasp the foundational concepts of algorithms in general.
Algorithm Steps
Start at the first two elements in the list
Compare those elements
Swap those elements if they're not sorted
Move to the next two elements and repeat steps 2 and 3
Repeat steps 1-4 till you reach the end of the list
Repeat steps 1-5 till the list is sorted
Code Snippet
def bubble_sort(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
Time complexity
Regardless of whether the list is partially sorted, or even fully sorted, bubble sort is a very slow algorithm.
This is because no matter what, you iterate through the list n - 1 times, and make 2 comparisons for each element included in each iteration.
This means that the bubble sort time complexity is
$$O(n^2)$$
This means that we need to make n^2 comparisons for a list of length n.
Bubble sort time complexity graph:
Advantages
The main advantage of bubble sort is that it's very simple for beginner software engineers to conceptually understand and implement into code.
Disadvantages
The biggest and most apparent of bubble sort is the incredible inefficiency.
Since the bubble sort time complexity is so large, it's rarely used in practice.
Insertion Sort
Insertion sort is another slow sorting algorithm but is usually faster than bubble sort.
Again, even though this algorithm is slow, it's a good algorithm to study as a beginner software engineer.
Insertion sort works by dividing the list into a sorted and an unsorted section. It iterates through the unsorted section, taking one element at a time and inserting it into its correct position in the sorted section. This process continues until all elements from the unsorted section have been inserted into the sorted section in the correct order.
Algorithm Steps
Start by pulling the second element in the list
Look at all the numbers to the left of the vacant spot and slide over all the values larger than the element we pulled out
Insert the element we pulled out into whatever spot is now vacant
Pull the next element out of the list
Repeat steps 2 and 3
Repeat step 4 until the entire list is sorted
Code snippet
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
Time complexity
The worst-case scenario for insertion sort is if the list starts in the complete reverse order.
In this worst-case scenario, the insertion sort algorithm makes this amount of comparisons:
$$\frac{1}{2} (n^2-n)$$
Therefore, the insertion sort time complexity is:
$$O(n^2)$$
If you notice, the insertion sort's time complexity is the same as the bubble sort's time complexity.
However, if a list is partially sorted (meaning some values are already in their correct index), then insertion sort takes less time than bubble sort.
The best case scenario for insertion sort is if the list is already sorted. If the list is already sorted, then insertion sort makes 0 list comparisons. On the other hand, bubble sort's time complexity will remain n^2 even for a fully sorted list.
Therefore, in practice, the insertion sort algorithm is usually much faster than the bubble sort algorithm since insertion sort will typically make fewer comparisons than bubble sort.
Advantages
The biggest advantage of insertion sort is that it's typically faster than the bubble sort algorithm, and the amount of comparisons it makes is dependent on how sorted the list already is. Whereas, bubble sort's time complexity is independent of how sorted the list already is.
Disadvantages
The main disadvantage of insertion sort is that it's still considered a pretty slow sorting algorithm.
Conclusion
I hope after reading this article, you now have a clearer understanding of the bubble sort and insertion sort algorithms and a more general understanding of the importance of studying algorithms in computer science.
In this article, you learned about the basic concept behind both the bubble sort and insertion sort algorithms, their steps, their implementation in Python code, their time complexity, and some of the advantages and disadvantages for both.
If you have any lingering questions or suggestions for an article you want me to cover in the future, feel free to leave a comment in the comment section below.
Lastly, make sure to follow my newsletter so you never miss out on when I post new content! When you subscribe to my newsletter, you'll be able to read my articles straight from your inbox as soon as they're released.
This article is part of a series called Bit by Bit, a series devoted to all things programming. Whether you're still a computer science undergrad or the CTO of Apple, there's something for you here.
New articles in this series are posted every Tuesday!
