Optimized Bubble Sort Algorithm in Python

Optimized Bubble Sort Algorithm 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 pass through the list is repeated until the list is sorted. An optimized version of Bubble Sort involves adding a flag to monitor whether any swaps were made during an iteration; if no swaps were made, the list is already sorted.

Key Points

1. Algorithm Explanation:

   • Compare adjacent elements and swap them if they are in the wrong order.
   • Track if any swaps happen in an iteration to identify early completion.
   • Continue this process for every element until no swaps are needed.

2. Optimization Technique:

   • Introduction of a "swapped" flag to terminate the sort early if the list is already sorted.

Optimized Bubble Sort Algorithm

Here is the code for the optimized Bubble Sort algorithm in Python:

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Last i elements are already sorted
        for j in range(0, n-i-1):
            # Traverse the array from 0 to 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 two elements were swapped by inner loop, then break
        if not swapped:
            break
    return arr

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort_optimized(arr)
print("Sorted array:", sorted_arr)

Explanation of the Code

• Outer Loop (for i in range(n)): Runs n times, where n is the length of the array.
• Inner Loop (for j in range(0, n-i-1)): Compares each pair of adjacent elements and swaps them if they are in the wrong order. The range decreases as the largest elements bubble to the end of the list, reducing needed comparisons.
• Swapped Flag (swapped = True/False): This flag checks if any swapping occurred in the current pass. If no swapping is done, it means the array is already sorted, and the algorithm can terminate early.

Advantages of the Optimized Version

• Early Termination: The algorithm stops early if the array becomes sorted before completing all iterations, improving performance in best-case scenarios.
• Same Time Complexity: In the worst case, the time complexity remains O(n^2), but average performance improves with early stopping.

This implementation ensures efficiency and simplicity. For further learning, consider exploring advanced sorting algorithms or Enterprise DNA's training courses on data analytics.