Sorting algorithms are like the unsung heroes in the world of programming. Whether it’s arranging high scores in a game, organizing player data, or even setting leaderboard standings, the act of sorting is pivotal in creating a sense of order and efficiency in our digital experiences. One of the earliest and simplest sorting techniques that budding programmers learn is the Bubble Sort. Easy to understand and implement, Bubble Sort is like the first step into a larger world of algorithmic thinking, problem-solving, and optimization.
What is Bubble Sort?
Table of contents
Understanding Bubble Sort
Bubble Sort is a straightforward sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The process continues until no more swaps are needed, indicating that the list is sorted. Think of it as watching air bubbles rise to the surface of water – hence the name.
What is it for?
Bubble Sort has its place in educational purposes and simple applications where the efficiency of the algorithm isn’t the primary concern. It’s a great tool for illustrating the basic concepts of algorithm design, such as iteration and swapping, and serves as a stepping stone toward more complex sorting algorithms.
Why Should I Learn It?
Learning Bubble Sort is more about grasping the fundamentals of sorting mechanisms and understanding algorithm efficiency than about utilizing it in production environments. What’s critical is the conceptual groundwork it lays for more advanced algorithmic strategies that you’ll encounter as your programming journey unfolds.
FREE COURSES AT ZENVA
LEARN GAME DEVELOPMENT, PYTHON AND MORE
AVAILABLE FOR A LIMITED TIME ONLY
Implementing Bubble Sort in Python
Let’s jump into the implementation of the Bubble Sort algorithm using Python. This code snippet shows the basic function:
def bubble_sort(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j] > array[j+1] :
array[j], array[j+1] = array[j+1], array[j]
return arrayIn the above code, we start by defining the function bubble_sort which takes ‘array’ as its parameter. The outer loop runs once for each element in the array, while the inner loop compares each pair of adjacent elements.
Optimizing Bubble Sort
While Bubble Sort is not the most efficient, we can make a small optimization to terminate it early if the list gets sorted before making the maximum number of passes:
def optimized_bubble_sort(array):
n = len(array)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
swapped = True
if not swapped:
break
return arrayIn this optimized version, we introduce a flag named ‘swapped’ to keep track of whether any elements were swapped during the current pass. If no elements are swapped, the array is already sorted, and we can terminate the loop early to save time.
Testing Bubble Sort
Now that we’ve implemented the Bubble Sort algorithm, let’s test it out with some example arrays:
# Example array
array = [64, 34, 25, 12, 22, 11, 90]
# Sorting the array using our bubble_sort function
sorted_array = bubble_sort(array)
print("Sorted array is:", sorted_array)This should output:
Sorted array is: [11, 12, 22, 25, 34, 64, 90]
Next, let’s test our optimized bubble sort:
# Example array
array = [64, 34, 25, 12, 22, 11, 90]
# Sorting the array using our optimized_bubble_sort function
optimized_sorted_array = optimized_bubble_sort(array)
print("Optimized sorted array is:", optimized_sorted_array)And again, this should output the sorted array:
Optimized sorted array is: [11, 12, 22, 25, 34, 64, 90]
Both implementations should yield the same result, but the optimized version may perform fewer iterations if the list becomes sorted early.
Visualizing Bubble Sort
Understanding how Bubble Sort works can be greatly enhanced by a visual representation. Let’s write a function that prints the array after each pass, so we can see the algorithm in action:
def bubble_sort_visual(array):
n = len(array)
for i in range(n):
print(f'Pass {i+1}:')
for j in range(0, n-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
print(array)
print("End of pass", i+1)
print()
return arrayRunning bubble_sort_visual with an example array allows us to observe the algorithm’s pass-by-pass execution:
# Example array array = [5, 1, 4, 2, 8] # Visualizing the array sorting after each pass bubble_sort_visual(array)
With each pass, you should see the largest element of that pass ‘bubble up’ to its correct position while the rest of the array progressively gets sorted.
In exploring Bubble Sort further, we could consider scenarios where different types of data need to be sorted. For instance, sorting a list of tuples based on the second value, or sorting a list of strings. Below are examples to illustrate these scenarios:
Sorting Tuples by Second Value
Suppose we have a list of tuples where each tuple represents a student’s name and their score. We want to sort this list based on the scores:
def bubble_sort_tuples(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j][1] > array[j+1][1]: # Compare based on the second tuple value
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of tuples
students_scores = [('Alice', 88), ('Bob', 95), ('Charlie', 70), ('Danielle', 96)]
# Sort the list of tuples
sorted_students_scores = bubble_sort_tuples(students_scores)
print(sorted_students_scores)After running the function, the students’ scores will be sorted in ascending order:
[('Charlie', 70), ('Alice', 88), ('Bob', 95), ('Danielle', 96)]Sorting Strings
Sorting strings is another practical application of Bubble Sort. In the following example, we’ll sort a list of strings based on their alphabetical order:
def bubble_sort_strings(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j].lower() > array[j+1].lower(): # Compare strings case-insensitively
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of strings
words = ['Banana', 'apple', 'Cherry', 'date']
# Sort the list of strings
sorted_words = bubble_sort_strings(words)
print(sorted_words)The sorted list will be:
['apple', 'Banana', 'Cherry', 'date']
Descending Order Sort
What if you need to sort an array in descending order? You simply change the comparison operation. Here’s how:
def bubble_sort_descending(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j] ' to '<' to sort in descending order
array[j], array[j+1] = array[j+1], array[j]
return array
# Example array
array = [3, 0, 2, 5, -1, 4, 1]
# Sorting the array in descending order
sorted_array_desc = bubble_sort_descending(array)
print(sorted_array_desc)Which will sort the array into:
[5, 4, 3, 2, 1, 0, -1]
Sorting with a Custom Comparator
In Python, you can also pass a custom comparator function to define a custom sorting order. Here is how you could sort an array of strings by their lengths using Bubble Sort:
def bubble_sort_by_length(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if len(array[j]) > len(array[j+1]): # Using the length of strings to compare
array[j], array[j+1] = array[j+1], array[j]
return array
# Example array
string_array = ['pear', 'apple', 'orange', 'banana', 'kiwi']
# Sorting by the length of the strings
sorted_strings_by_length = bubble_sort_by_length(string_array)
print(sorted_strings_by_length)The resulting sorted array by string length:
['pear', 'kiwi', 'apple', 'orange', 'banana']
Through these examples, it’s evident that Bubble Sort is versatile in the sense that it can handle different types of data. Although not the most efficient for large datasets or performance-critical applications, Bubble Sort provides a solid foundational understanding of sorting algorithms. It demonstrates how simple changes can adapt the process to different sorting criteria, ultimately enriching our algorithmic toolkit.
At Zenva, we value the importance of foundational knowledge and encourage learners to explore sorting algorithms in-depth. Understanding these core concepts is essential to become proficient in programming, algorithm design, and problem-solving. Our courses provide a hands-on approach to learning these skills, ensuring that students are well-equipped to tackle complex challenges in the future.
Bubble Sort can be further extended to accommodate even more complex structures, such as sorting objects based on their attributes or nested structures based on a specific key. Let’s look at some examples where Bubble Sort can be adapted to handle these scenarios.
Suppose we have a list of objects where each object represents a book with a title and number of pages. To sort this list by the number of pages, we would adjust our Bubble Sort function as follows:
class Book:
def __init__(self, title, pages):
self.title = title
self.pages = pages
def bubble_sort_books(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j].pages > array[j+1].pages: # Sort by the number of pages
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of Book objects
book_list = [Book('Book A', 230), Book('Book B', 120), Book('Book C', 320)]
# Sorted books by the number of pages
sorted_books = bubble_sort_books(book_list)
for book in sorted_books:
print(f'{book.title}: {book.pages} pages')This code would output the books sorted by their number of pages:
Book B: 120 pages Book A: 230 pages Book C: 320 pages
Moving beyond basic types, let’s look at sorting complex nested data structures, such as lists of dictionaries. We could sort a list of employees’ dictionaries by their age:
def bubble_sort_by_age(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j]['age'] > array[j+1]['age']: # Sort by 'age' key
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of employee dictionaries
employees = [
{'name': 'John', 'age': 45},
{'name': 'Marie', 'age': 32},
{'name': 'Andrew', 'age': 29}
]
# Sorting employees by age
sorted_employees = bubble_sort_by_age(employees)
for emp in sorted_employees:
print(f"{emp['name']}: {emp['age']} years old")The sorted result:
Andrew: 29 years old Marie: 32 years old John: 45 years old
Now let’s see how Bubble Sort can be used to sort based on a custom criterion, for example: sorting a list of strings by the number of vowels they contain, which is a non-standard sorting criterion that may come up in more unique programming contexts.
def count_vowels(string):
vowels = 'aeiouAEIOU'
return sum(1 for char in string if char in vowels)
def bubble_sort_by_vowels(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if count_vowels(array[j]) > count_vowels(array[j+1]): # Use the count_vowels function
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of strings
strings = ['hello', 'world', 'I', 'am', 'writing', 'code']
# Sorting strings by the number of vowels
sorted_strings_by_vowels = bubble_sort_by_vowels(strings)
print(sorted_strings_by_vowels)After sorting, the list of strings ordered by the number of vowels would output like this:
['I', 'am', 'world', 'code', 'hello', 'writing']
Lastly, Bubble Sort can also be adapted to work with multi-criteria sorting. For example, sorting a list of tuples first by one element, then by another if the first is equal. This is known as stable sorting, which keeps the relative order of equal elements intact.
def bubble_sort_stable(array):
n = len(array)
for i in range(n):
for j in range(0, n-i-1):
if array[j][0] > array[j+1][0] or (array[j][0] == array[j+1][0] and array[j][1] > array[j+1][1]):
array[j], array[j+1] = array[j+1], array[j]
return array
# Example list of tuples with two elements
tuples = [(1, 'b'), (3, 'a'), (2, 'a'), (2, 'b'), (1, 'a')]
# Sorting tuples using stable Bubble Sort
sorted_tuples = bubble_sort_stable(tuples)
print(sorted_tuples)This will maintain the tuples with equal first elements in their original relative order:
[(1, 'b'), (1, 'a'), (2, 'a'), (2, 'b'), (3, 'a')]
These examples illustrate that by customizing the comparison operation, Bubble Sort can be turned into a versatile sorting tool for a broad range of applications, from the most straightforward to those requiring thoughtful consideration of the data’s structure. Grasping this algorithm paves the way for understanding more sophisticated ones, a journey you can continue with us at Zenva, where we delve into the intricacies of efficient computing and algorithmic problem-solving.
Continue Your Programming Journey with Zenva
Now that you’ve gotten a taste of algorithmic thinking and explored the world of Bubble Sort, you’re likely eager to keep expanding your programming horizons. To continue building on your newfound knowledge, we encourage you to dive into our Python Mini-Degree, a thorough compilation of Python courses that will take you from the basics of coding to creating your own impressive applications and games.
Whether you’re a complete novice or looking to sharpen your technical skills further, our Python Mini-Degree is designed to suit your learning pace. With a hands-on approach, you’ll gain practical experience by coding real-world projects, which will help you solidify your understanding and prepare you for a future in technology. Plus, our interactive lessons, coding challenges, and quizzes are sure to keep your learning engaging and on track.
For those of you who wish to explore beyond Python and venture into other areas of programming, we’ve got you covered. Have a look at our broad selection of Programming courses, where you can find a wealth of resources to turn those coding dreams into reality. Remember, at Zenva, we’re here to support your journey from beginner to professional, and we’re excited to see where your newfound skills will take you.
Conclusion
Algorithms like Bubble Sort are more than just code; they’re the building blocks of logical thinking and problem-solving in programming. Understanding such algorithms is essential, whether you’re sorting players in a game or organizing complex data. By starting with these basics, you’re not only learning how to code, but also how to think like a programmer. This foundational knowledge is powerful, and with each step, you’re unlocking new potential and capabilities in the exciting world of technology.
Remember, our Python Mini-Degree is the perfect next step to further your education. Whether your interests lie in data manipulation, web development, or even game design, our comprehensive program will provide the skills you need to excel. At Zenva, we’re committed to helping our students thrive. Take the leap—master the logic, embrace the challenges, and transform your future with coding.
FREE COURSES
FINAL DAYS: Unlock coding courses in Unity, Unreal, Python, Godot and more.
