September 11, 2024

Python Tutorials

How to Implement Bubble Sort in Python

Bubble sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted. Below is an implementation of bubble sort in Python.

Bubble Sort Algorithm

The basic idea of bubble sort is to compare each pair of adjacent elements and swap them if they are in the wrong order. The largest unsorted element “bubbles up” to its correct position after each pass through the list.

Example:

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all elements in the list
    for i in range(n):
        # Flag to detect any swap
        swapped = False
        # Last i elements are already sorted
        for j in range(0, 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 list is already sorted
        if not swapped:
            break

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

Output:

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

Explanation

In this implementation:

  • The outer loop runs n times, where n is the length of the list. After each iteration, the largest unsorted element is placed in its correct position.
  • The inner loop compares adjacent elements and swaps them if they are in the wrong order.
  • A swapped flag is used to detect whether any swaps were made during a pass. If no swaps were made, the list is already sorted, and the algorithm can terminate early.

Optimizations

The bubble sort algorithm can be optimized by detecting whether the list is already sorted, as shown with the swapped flag in the above example. If no elements are swapped during a pass, the algorithm terminates early.

Time Complexity

Bubble sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list. This makes it inefficient on large lists, and generally, other more efficient algorithms like quicksort, mergesort, or heapsort are used for larger datasets.

You May Like