Bubble Sort in Python: Program, Complexity, Working
Introduction
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. While it may not be the most efficient sorting algorithm for large datasets, it is easy to understand and implement, making it a valuable learning tool for beginners. In this comprehensive guide, we’ll explore the principles behind Bubble Sort and provide a step-by-step implementation in Python.
Table of contents
Bubble Sort Algorithm
Bubble Sort is a comparison-based algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. The algorithm gets its name from how smaller elements “bubble” to the top of the list during each iteration.
Bubble Sort Program in Python
To implement Bubble Sort in Python, we follow a step-by-step algorithm. First, we compare adjacent elements and swap them if necessary. We repeat this process for each pair of adjacent elements until the entire list is sorted. We provide a code example below to illustrate the implementation.
Below is a simple implementation of the Bubble Sort algorithm in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# Example usage
my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print(sorted_list)Time Complexity Analysis of Bubble Sort
The time complexity of Bubble Sort is O(n^2), where n is the number of elements in the list. This means the algorithm’s performance decreases significantly as the list size increases. However, Bubble Sort can be efficient for small datasets or partially sorted lists.
How Bubble Sort Works in Python
To implement Bubble Sort in Python, we compare and swap the first two elements if necessary. We then move to the next pair of elements and continue this process until the end of the list. This constitutes one pass. We repeat this process for multiple passes until the list is completely sorted.
Here is the illustration of how Bubble Sort works
Step 1: Our input Array is {7,4,1,6}
Step 2:
Step 3:
Optimizing Bubble Sort in Python
While Bubble Sort is not the most efficient sorting algorithm, several optimization techniques can improve its performance. Here, you will learn about the 3 bubble sorting techniques: Flagged Bubble Sort, Recursive Bubble Sort, and Cocktail Shaker Sort.
- Flagged Bubble Sort uses a flag to track whether swaps were made during a pass. If no swaps occur, the list is sorted, and we can terminate the algorithm early.
- Recursive Bubble Sort is a variation of Bubble Sort that uses recursion to sort the list. It divides the list into two parts: the first element and the remaining unsorted list. It then recursively sorts the remaining list until the entire list is sorted.
- Cocktail Shaker Sort, also known as Bidirectional Bubble Sort, is an optimized version of Bubble Sort that sorts the list in both directions. This reduces the required passes and can improve the algorithm’s performance.
Bubble Sort Applications and Use Cases
Bubble Sort can be applied in various scenarios where sorting is required. It is commonly used for sorting lists, arrays, and data structures such as linked lists and binary trees. Additionally, Bubble Sort can handle large datasets, although its performance may be slower than that of more efficient sorting algorithms. Here are the applications of Bubble Sort:
- Sorting Lists and Arrays: Bubble Sort can sort lists and arrays of any data type. It is particularly useful when the list is small or partially sorted.
- Sorting Data Structures: Bubble Sort can be applied to sort data structures like linked lists and binary trees. However, its performance may not be optimal for large data structures.
- Sorting Large Datasets: While Bubble Sort is not the most efficient algorithm for sorting large datasets, it can still be used if performance is not critical. However, it is recommended that more efficient sorting algorithms for large datasets be considered.
Bubble Sort vs Other Sorting Algorithms
Sorting algorithms are essential in computer science, and various algorithms have been developed to organize data efficiently. To understand their differences and performance characteristics, let’s compare Bubble Sort with a few other popular sorting algorithms.
- Bubble Sort vs Selection Sort: Both algorithms have a time complexity of O(n^2), but Selection Sort performs fewer swaps, making it more efficient in practice.
- Bubble Sort vs Insertion Sort: Insertion Sort is another comparison-based sorting algorithm that builds the final sorted list one element at a time. It performs better than Bubble Sort for small datasets and partially sorted lists.
- Bubble Sort vs Merge Sort: Merge Sort is a divide-and-conquer algorithm that divides the list into smaller sublists, sorts them, and then merges them. It has a time complexity of O(n log n) and is more efficient than Bubble Sort for large datasets.
- Bubble Sort vs Quick Sort: Quick Sort is another divide-and-conquer algorithm that partitions the list into two sublists, sorts them independently, and then combines them. It has an average time complexity of O(n log n) and is generally faster than Bubble Sort.
Conclusion
In this comprehensive guide, we explored the Bubble Sort algorithm in Python. Its working principle analyzed its time complexity and explored various optimization techniques. We also compared Bubble Sort with other sorting algorithms and provided a step-by-step implementation in Python. We also discussed the applications and use cases of Bubble Sort, as well as best practices and tips for efficient usage. Following the guidelines and techniques outlined in this guide, you can effectively apply Bubble Sort to your projects and achieve the desired sorting results. If you want a complete AI & ML program, register yourself @Certified AI & ML BlackBelt Plus Program today.
