mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
VARNIT KUMARandpre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
42ae7a6521
* feat: add recursive bubble sort algorithm with doctests and type hints Implement recursive Bubble Sort algorithm with doctests. * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Refactor bubble_sort_recursive function Refactor bubble_sort_recursive to use built-in list type and improve return statement. --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
36 lines
799 B
Python
36 lines
799 B
Python
def bubble_sort_recursive(arr: list[int]) -> list[int]:
|
|
"""
|
|
Sorts a list of integers using the recursive Bubble Sort algorithm.
|
|
|
|
>>> bubble_sort_recursive([5, 1, 4, 2, 8])
|
|
[1, 2, 4, 5, 8]
|
|
>>> bubble_sort_recursive([])
|
|
[]
|
|
>>> bubble_sort_recursive([1])
|
|
[1]
|
|
>>> bubble_sort_recursive([3, 3, 2, 1])
|
|
[1, 2, 3, 3]
|
|
>>> bubble_sort_recursive([-1, 5, 0, -2])
|
|
[-2, -1, 0, 5]
|
|
"""
|
|
n = len(arr)
|
|
if n <= 1:
|
|
return arr
|
|
|
|
swapped = False
|
|
for i in range(n - 1):
|
|
if arr[i] > arr[i + 1]:
|
|
arr[i], arr[i + 1] = arr[i + 1], arr[i]
|
|
swapped = True
|
|
|
|
if not swapped:
|
|
return arr
|
|
|
|
return [*bubble_sort_recursive(arr[:-1]), arr[-1]]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod()
|