Explanation

• Concept: Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
• Process: The algorithm gets its name because smaller elements 'bubble' to the top of the list.
• Steps:
  • Compare each pair of adjacent elements.
  • If the elements are in the wrong order, swap them.
  • Repeat the process for each element until the list is sorted.
• Efficiency: Bubble sort has a time complexity of O(n^2) for the worst and average cases, making it inefficient for large datasets. However, it is simple to implement and understand.

Python Implementation

      
          from typing import List

def bubble_sort(arr: List[int]) -> List[int]:
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = bubble_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [64, 25, 12, 22, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 12, 22, 11] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [11, 12, 22, 25, 64]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [64, 25, 22, 12, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 22, 12, 11] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [64, 25, 12, 22, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [11, 12, 22, 25, 64], "expected": [11 ,12, 22, 25, 64]},
        {"input": [64, 25, 22, 12, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = bubble_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()