Bubble Sort Algorithm

Bubble Sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. The algorithm works by comparing each pair of adjacent elements and swapping them if they are in the wrong order. This process continues until all the elements are sorted.

Here’s how the algorithm works in detail:

1. Start from the first element of the array and compare it with the next element.
2. If the first element is greater than the next element, swap them.
3. Move to the next pair of elements and repeat step 2.
4. Continue this process until all the pairs of elements have been compared and swapped if necessary.
5. After the first pass, the largest element will be at the end of the array.
6. Repeat the same process for the rest of the array, excluding the last element, which is already sorted.
7. Continue this process until the whole array is sorted.

Bubble sort has a time complexity of O(n^2), which makes it not suitable for sorting large arrays. However, it’s a good algorithm to understand the basics of sorting algorithms and it’s simple to implement.

Code Example

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Keep track of whether any swaps were made during this pass
        swapped = False
        # Last i elements are already in place, no need to check them
        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 elements were swapped, the array is already sorted
        if not swapped:
            break
    return arr

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

Code Explanation

1. Initialization:
   • The n variable stores the length of the input list arr.
2. Outer Loop:
   • The outer loop runs n times, ensuring that every element is correctly positioned by the end of the algorithm. However, it can break early if no swaps were made in a pass, indicating that the list is already sorted.
3. Inner Loop:
   • The inner loop compares adjacent elements and swaps them if they are in the wrong order. It runs fewer times with each subsequent pass, as the largest elements “bubble up” to their correct positions.
4. Swapped Flag:
   • A boolean flag swapped is used to detect whether any elements were swapped during a pass. If no swaps were made, the algorithm terminates early.
5. Example Usage:
   • An example list arr is sorted using the bubble_sort function, and the sorted list is printed.

Execution Process:

1. Initial Array: [64, 34, 25, 12, 22, 11, 90]

Pass 1:

• Compare 64 and 34 -> swap: [34, 64, 25, 12, 22, 11, 90]
• Compare 64 and 25 -> swap: [34, 25, 64, 12, 22, 11, 90]
• Compare 64 and 12 -> swap: [34, 25, 12, 64, 22, 11, 90]
• Compare 64 and 22 -> swap: [34, 25, 12, 22, 64, 11, 90]
• Compare 64 and 11 -> swap: [34, 25, 12, 22, 11, 64, 90]
• Compare 64 and 90 -> no swap: [34, 25, 12, 22, 11, 64, 90]

Pass 2:

• Compare 34 and 25 -> swap: [25, 34, 12, 22, 11, 64, 90]
• Compare 34 and 12 -> swap: [25, 12, 34, 22, 11, 64, 90]
• Compare 34 and 22 -> swap: [25, 12, 22, 34, 11, 64, 90]
• Compare 34 and 11 -> swap: [25, 12, 22, 11, 34, 64, 90]
• Compare 34 and 64 -> no swap: [25, 12, 22, 11, 34, 64, 90]

Pass 3:

• Compare 25 and 12 -> swap: [12, 25, 22, 11, 34, 64, 90]
• Compare 25 and 22 -> swap: [12, 22, 25, 11, 34, 64, 90]
• Compare 25 and 11 -> swap: [12, 22, 11, 25, 34, 64, 90]
• Compare 25 and 34 -> no swap: [12, 22, 11, 25, 34, 64, 90]

Pass 4:

• Compare 12 and 22 -> no swap: [12, 22, 11, 25, 34, 64, 90]
• Compare 22 and 11 -> swap: [12, 11, 22, 25, 34, 64, 90]
• Compare 22 and 25 -> no swap: [12, 11, 22, 25, 34, 64, 90]

Pass 5:

• Compare 12 and 11 -> swap: [11, 12, 22, 25, 34, 64, 90]
• Compare 12 and 22 -> no swap: [11, 12, 22, 25, 34, 64, 90]

Pass 6:

• No swaps, so the loop terminates early.

Final Sorted Array

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

Output

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