Sorting is a fundamental operation in computer science, playing a crucial role in optimizing search and retrieval tasks. One of the simplest yet widely used sorting algorithms is Bubble Sort. In this blog, we'll dive into the mechanics of Bubble Sort, provide Python code examples, solve a LeetCode problem using Bubble Sort, and even explore a fun fact about its name!

Bubble Sort Explained

Bubble Sort is a straightforward comparison-based sorting algorithm. It repeatedly steps through the list of elements to be sorted, compares adjacent items, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. While Bubble Sort is not the most efficient sorting algorithm for large datasets, it serves as a great educational tool due to its simplicity.

Here's how Bubble Sort works in a nutshell:

1. Start from the beginning of the list.

2. Compare each pair of adjacent items.

3. If they are in the wrong order, swap them.

4. Move to the next pair and repeat.

5. Continue until no more swaps are needed, indicating a sorted list.

Python Implementation of Bubble Sort

Let's implement Bubble Sort 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

Solving a LeetCode Problem using Bubble Sort

Problem: LeetCode 912 - Sort an Array

Given an array of integers, use Bubble Sort to sort the array in ascending order.

def sortArray(nums):
    return bubble_sort(nums)

Fun Fact: Why "Bubble" Sort?

The name "Bubble Sort" comes from the way smaller elements "bubble" to the top of the list while larger elements "sink" to the bottom. The algorithm's repetitive swapping resembles the movement of bubbles rising to the surface in a liquid. While Bubble Sort might not be the most efficient sorting algorithm, its name adds a touch of whimsy to the world of computer science.

Conclusion

Bubble Sort might not be the most efficient sorting algorithm, but it provides valuable insights into the world of sorting algorithms. By implementing Bubble Sort in Python, we've explored the step-by-step process of arranging elements. Additionally, we've solved a LeetCode problem using Bubble Sort, highlighting its practical application.

Next time you hear "Bubble Sort," remember its rise-and-sink analogy and the valuable lessons it offers in understanding sorting algorithms. Whether you're a budding programmer or a seasoned coder, Bubble Sort is a fundamental concept worth exploring on your journey to mastering algorithms.

Oh! Wait Bouns Problem solution

Bouns: "Remove Duplicates from Sorted Array" (LeetCode Problem #26).

Problem Statement: Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Here's the Bubble Sort solution:

def removeDuplicates(nums):
    n = len(nums)
    if n == 0:
        return 0

    new_length = 1  # Initialize new length with 1 (since the first element is unique)

    for i in range(1, n):
        if nums[i] != nums[i - 1]:  # Compare with the previous element
            nums[new_length] = nums[i]  # Move unique element to the correct position
            new_length += 1

    return new_length

In this solution, we're using Bubble Sort-like logic to remove duplicates while maintaining the sorted order. The variable new_length keeps track of the position where unique elements should be placed. As we iterate through the array, if the current element is not equal to the previous element, it means we've found a new unique element. We then move this unique element to the correct position indicated by new_length.

For example, given the input [1, 1, 2, 2, 3], after applying the removeDuplicates function, the array will become [1, 2, 3, 2, 3], and the function will return 3 (indicating the new length).

Bubble Sort isn't the most efficient algorithm for this problem, but it demonstrates how sorting algorithms' concepts can be adapted for different tasks. More efficient algorithms like two-pointer approach or Python's set could be used to solve this problem faster.

Remember that Bubble Sort's primary purpose is sorting, and it's not the most efficient choice for removing duplicates from a sorted array. However, the approach used in this solution showcases how fundamental sorting concepts can be applied creatively to various problems.
Happy coding and sorting! 🚀🔍🧠