Bubble Sort Algorithm in Python | Explained in Depth

Hi everyone! In this article, we’ll help you solve & understand bubble sort algorithm in Python like nowhere before. With it’s approach, code, explanation, dry run & complexity analysis.

So let’s begin with the [Problem Link].

Problem Statement

Given an array, “arr[]”. Sort the array using bubble sort algorithm.

Examples

Example 1:

  Input: arr[] = [4, 1, 3, 9, 7]
  Output: [1, 3, 4, 7, 9]

Example 2:

  Input: arr[] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Example 3:

  Input: arr[] = [1, 2, 3, 4, 5]
  Output: [1, 2, 3, 4, 5]
  Explanation: An array that is already sorted should remain unchanged after applying bubble sort.

Constraints:

• 1 <= arr.size() <= 10³
• 1 <= arr[i] <= 10³

Approach to Bubble Sort Algorithm in Python

The bubble sort algorithm works by repeatedly comparing adjacent elements in the array & swapping them if they are in the wrong order.

This process is repeated for every element. Ensuring that after each pass, the largest unsorted element is “bubbled” to its correct position. The algorithm continues until the array is sorted.

Key Steps in the Approach:

1. Start with the first element and compare it with the next
2. If the current element is greater than the next, swap them
3. Move to the next pair of elements and repeat the process for the entire array
4. After each pass, the largest unsorted element is placed at its correct position
5. Reduce the range of comparison for subsequent passes as the largest elements are already sorted
6. Repeat this process until no swaps are needed or the array is sorted

Also read about the Python Program for Selection Sort Algorithm.

Code

class Solution:
    # Function to sort the array using bubble sort algorithm.
    def bubbleSort(self, arr):
        n = len(arr)
        for i in range(n - 2, -1, -1):
            for j in range(0, i + 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

Code Explanation

1. Class & Function Definition:
   1. A class Solution is defined, which contains the method “bubbleSort”
   2. The function takes one parameter, “arr”, which is the array to be sorted
2. Initialization: n = len(arr): The length of the array is stored in the variable “n”
3. Outer Loop (for i in range(n – 2, -1, -1)):
   1. This loop controls the number of passes through the array
   2. It runs from n-2 to 0 (inclusive), ensuring that with each iteration, the unsorted portion of the array reduces by one
4. Inner Loop (for j in range(0, i + 1)):
   1. This loop iterates through the unsorted portion of the array
   2. “j” starts from the beginning of the array and goes up to the last unsorted element (i + 1)
5. Comparison (if arr[j] > arr[j + 1]): Adjacent elements are compared to check if they are in the wrong order (i.e., the current element is greater than the next)
6. Swapping (arr[j], arr[j + 1] = arr[j + 1], arr[j]): If the elements are out of order, they are swapped using Python’s tuple unpacking
7. Termination: After the outer loop completes all passes, the array is sorted

Dry Run

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Complexity Analysis

1. Time Complexity:
   • Worst Case: O(n²), when the array is in reverse order and every element needs to be compared and swapped
   • Best Case: O(n²), as the given code does not include an optimization to exit early when the array is already sorted
   • Average Case: O(n²)
2. Space Complexity:
   • The algorithm operates in-place, meaning no extra memory is used apart from a few variables
   • Space Complexity: O(1)

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.