Bubble Sort Algorithm in Python.

Sorting algorithms play an important role in organizing data efficiently. One such algorithm is the Bubble Sort Algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In this article, we will understand the algorithm in detail with implementation in Python code.

Bubble Sort Algorithm for 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. It proceeds until no more swaps are needed, indicating that the list is sorted.

Algorithm Steps:

Start from the beginning of the list.
Compare adjacent elements.
Swap them if they are in the wrong order.
Repeat steps 2 and 3 until the entire list is sorted.

Python Code Implementation of Bubble Sort.

Here is an example of Bubble Sort in Python:

# Python code for Bubble Sort Algorithm
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):

        # Flag to optimize when the list is already sorted
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no two elements were swapped, the list is sorted
        if not swapped:
            break

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

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Time and Space Complexity.

Time Complexity: O(n^2) in the worst-case scenario, as it involves nested loops iterating through the array. Best-case scenario (when the list is already sorted) can be O(n).

Space Complexity: O(1) as Bubble Sort operates in place, requiring only a constant amount of extra space for variables.

Explanation of Bubble Sort With Example.

Let's consider the example [64, 34, 25, 12, 22, 11, 90] and step through the Bubble Sort process:

Step 1: Comparing adjacent elements and swapping them if necessary.

[34, 25, 12, 22, 11, 64, 90]
[25, 12, 22, 11, 34, 64, 90]
[12, 22, 11, 25, 34, 64, 90]
[12, 11, 22, 25, 34, 64, 90]
[11, 12, 22, 25, 34, 64, 90]

Step 2: Continuing comparisons and swaps.

[11, 12, 22, 25, 34, 64, 90]

Step 3: The array is sorted in ascending order.

Bubble Sort is generally inefficient for larger datasets due to its quadratic time complexity. However, it can be suitable for small datasets or nearly sorted arrays. Other sorting algorithms like Merge Sort or Quick Sort offer better performance for larger datasets.