def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(len(lst)-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

# Test cases
print(bubble_sort([]))  # Empty list
print(bubble_sort([1]))  # Single element
print(bubble_sort([3, 2, 1]))  # Reverse sorted list
print(bubble_sort([1, 2, 3]))  # Sorted list
print(bubble_sort([5, 2, 8, 1, 9]))  # Random list

def test_selection_sort():
    # Test case 1: Empty list
    lst = []
    assert selection_sort(lst) == []

    # Test case 2: List with one element
    lst = [5]
    assert selection_sort(lst) == [5]

    # Test case 3: List with multiple elements in ascending order
    lst = [1, 2, 3, 4, 5]
    assert selection_sort(lst) == [1, 2, 3, 4, 5]

    # Test case 4: List with multiple elements in descending order
    lst = [5, 4, 3, 2, 1]
    assert selection_sort(lst) == [1, 2, 3, 4, 5]

    # Test case 5: List with multiple elements in random order
    lst = [3, 1, 4, 2, 5]
    assert selection_sort(lst) == [1, 2, 3, 4, 5]

    # Test case 6: List with duplicate elements
    def test_selection_sort():
        lst = [3, 1, 4, 2, 5, 1, 2, 3, 4, 5]
        assert selection_sort(lst) == [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

        print("All test cases pass")

    test_selection_sort()

    def bubble_sort(lst):
        for i in range(len(lst)):
            for j in range(len(lst)-1):
                if lst[j] > lst[j+1]:
                    lst[j], lst[j+1] = lst[j+1], lst[j]
        return lst

    # Test case 1: Empty list
    input_list = []
    expected_output = []
    assert bubble_sort(input_list) == expected_output

    # Test case 2: List with one element
    input_list = [5]
    expected_output = [5]
    assert bubble_sort(input_list) == expected_output

    # Test case 3: List with multiple elements in ascending order
    input_list = [1, 2, 3, 4, 5]
    expected_output = [1, 2, 3, 4, 5]
    assert bubble_sort(input_list) == expected_output

    # Test case 4: List with multiple elements in descending order
    input_list = [5, 4, 3, 2, 1]
    expected_output = [1, 2, 3, 4, 5]
    assert bubble_sort(input_list) == expected_output

    # Test case 5: List with multiple elements in random order
    input_list = [3, 1, 4, 2, 5]
    expected_output = [1, 2, 3, 4, 5]
    assert bubble_sort(input_list) == expected_output

    print("All test cases passed!")
