← Back to Data Structures and Algorithms in Python

1. Introduction

The Bubble Sort algorithm is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues this process until no more swaps are needed, which indicates that the list is sorted.

2. Implementation Steps

1. Start iterating from the beginning of the list.

2. Compare each pair of adjacent items.

3. If a pair is in the wrong order, swap them.

4. Continue doing this for each pair of adjacent items until the end of the list is reached.

5. Repeat the above steps for every element in the list.

6. When no more swaps are needed, the list is sorted.

3. Implementation in Python

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all elements in the list
    for i in range(n):
        # Set a flag to check if any swaps occurred in this pass
        swapped = False
        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Traverse the list from 0 to n-i-1
            # Swap if the current element 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 in the inner loop, the list is already sorted
        if not swapped:
            break
    return arr
# Test the bubble_sort function
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)

Output:

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

Explanation:

1. We define the bubble_sort function that takes a list arr as its argument.

2. Inside the function, we get the length of the list n.

3. We then iterate over the list n times.

4. For each iteration, we set a swapped flag to False. This will help us identify if any swaps occurred in this pass.

5. We then iterate over the list again, this time from the start-up to n-i-1. This is because the last i elements are already in their correct position.

6. Inside the inner loop, if the current element arr[j] is greater than the next element arr[j+1], we swap them.

7. If at the end of an outer loop iteration, no swaps were made, we break out of the loop early. This is an optimization to make the algorithm run faster for nearly sorted lists.

8. Finally, we return the sorted list.

Note: Bubble Sort is not the most efficient sorting algorithm for larger lists, but it serves as a great introduction to the world of sorting algorithms.