Python: Bubble Sort on Lists

1. Introduction

In this blog post, we will learn how to write a Python program to implement Bubble Sort on a list.

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

2. Program Overview

In this program, we will:

1. Define the bubbleSort function which will sort the list using the Bubble Sort algorithm.

2. Test the bubble sort implementation on a sample list.

3. Code Program

def bubbleSort(arr):
    # Length of the array
    n = len(arr)

    # Traverse through all elements in the list
    for i in range(n):

        # Flag to optimize and check if any swap happened
        swapped = False

        # Last i elements are already in place, so we don't check them
        for j in range(0, n-i-1):

            # Traverse the list 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 in the inner loop, the list is already sorted
        if not swapped:
            break

# Test the function
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("Sorted array is:", arr)

Output:

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

4. Step By Step Explanation

1. The outer loop runs for each element of the list.

2. The inner loop checks pairs of elements starting from the beginning of the list. If the pair of elements is out of order, they are swapped.

3. After each pass of the outer loop, the largest unsorted element has "bubbled up" to its correct position.

4. To optimize the process, we introduce a swapped flag. If no swap occurred during a pass, it means the list is already sorted, and we can break out of the loop.