Bubble Sort

Bubble Sort

Bubble Sort is a comparison-based sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order.  The algorithm continues to iterate until the list is sorted.


Here is the step-by-step process of Bubble Sort:

The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each pass. Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list. It is not considered an efficient sorting algorithm for large data sets but can be useful for small or nearly sorted lists due to its simplicity and ease of implementation.

Although Bubble Sort is not efficient compared to other sorting algorithms, it has some advantages. It is easy to understand and implement, requires minimal additional memory, and performs well for small input sizes or partially sorted lists. However, for larger data sets, other sorting algorithms like Quick Sort or Merge Sort are generally preferred.

Bubble Sort Code in Python

Here's an implementation of the Bubble Sort algorithm in Python:

def bubble_sort(arr):

    n = len(arr)

    # Traverse through all array elements

    for i in range(n):

        # Last i elements are already in place

        for j in range(0, n-i-1):

            # Swap if the element found is greater than the next element

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:

array = [5, 2, 8, 1, 9, 3]

bubble_sort(array)

print("Sorted array:", array)

Optimized Bubble Sort

An optimized version of Bubble Sort is called "Optimized Bubble Sort" or "Flagged Bubble Sort". It improves the algorithm's efficiency by introducing a flag that keeps track of whether any swaps were made in a pass. If no swaps are made, it means the array is already sorted, and the algorithm can terminate early.


Here's the code for the optimized Bubble Sort in Python:

def bubble_sort(arr):

    n = len(arr)

    # Traverse through all array elements

    for i in range(n):

        # Initialize a flag to track if any swaps were made in the current pass

        swapped = False

        # Last i elements are already in place

        for j in range(0, n-i-1):

            # Swap if the element found is greater than the next element

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

                swapped = True

        # If no swaps were made in the current pass, the array is already sorted

        if not swapped:

            break

# Example usage:

array = [5, 2, 8, 1, 9, 3]

bubble_sort(array)

print("Sorted array:", array)

In this optimized version, the swapped flag is initially set to False. After each pass, if no swaps were made (i.e., swapped remains False), it means the array is sorted and the algorithm can terminate early by breaking out of the outer loop.