In this article, you will learn how to implement bubble sort in Python.
Bubble Sort in Python
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. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Here’s one way to implement bubble sort in Python:
def bubble_sort(list): n = len(list) for i in range(n): for j in range(0, n - i - 1): if list[j] > list[j + 1]: list[j], list[j + 1] = list[j + 1], list[j] return list
You can use this function to sort a list in ascending order by simply calling bubble_sort(list). For example:
list = [64, 34, 25, 12, 22, 11, 90] print("Sorted list:", bubble_sort(list)) # Output # Sorted list: [11, 12, 22, 25, 34, 64, 90]
In the code above, the outer loop for i in range(n) runs n times, where n is the length of the list. The inner loop for j in range(0, n – i – 1) runs n – i – 1 times, where i is the current iteration of the outer loop.
The reason for n – i – 1 is because after each iteration of the outer loop, the largest element in the list is placed at the end of the list, so it is no longer necessary to consider that element in subsequent comparisons.
In each iteration of the inner loop, we compare the current element list[j] with the next element list[j + 1] and if the current element is greater than the next element, we swap them.
Finally, the sorted list is returned.
It’s worth noting that bubble sort is not a very efficient sorting algorithm, especially for large lists. Its time complexity is O(n^2), which means that it can become very slow for large lists. There are many other sorting algorithms that have better time complexity and are more efficient, such as quicksort, mergesort, and heapsort. However, bubble sort is a good choice for small lists or for educational purposes, as it is easy to understand and implement.