Python/sorts/bubble_sort.py at master · TheAlgorithms/Python · GitHub

Name: Python/sorts/bubble_sort.py at master · TheAlgorithms/Python · GitHub
Rating: 4.8 (542 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
fromtypingimportAny


defbubble_sort_iterative(collection: list[Any]) ->list[Any]:
"""Pure implementation of bubble sort algorithm in Python

 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending

 Examples:
 >>> bubble_sort_iterative([0, 5, 2, 3, 2])
 [0, 2, 2, 3, 5]
 >>> bubble_sort_iterative([])
 []
 >>> bubble_sort_iterative([-2, -45, -5])
 [-45, -5, -2]
 >>> bubble_sort_iterative([-23, 0, 6, -4, 34])
 [-23, -4, 0, 6, 34]
 >>> bubble_sort_iterative([0, 5, 2, 3, 2]) == sorted([0, 5, 2, 3, 2])
 True
 >>> bubble_sort_iterative([]) == sorted([])
 True
 >>> bubble_sort_iterative([-2, -45, -5]) == sorted([-2, -45, -5])
 True
 >>> bubble_sort_iterative([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34])
 True
 >>> bubble_sort_iterative(['d', 'a', 'b', 'e']) == sorted(['d', 'a', 'b', 'e'])
 True
 >>> bubble_sort_iterative(['z', 'a', 'y', 'b', 'x', 'c'])
 ['a', 'b', 'c', 'x', 'y', 'z']
 >>> bubble_sort_iterative([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6])
 [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7]
 >>> bubble_sort_iterative([1, 3.3, 5, 7.7, 2, 4.4, 6])
 [1, 2, 3.3, 4.4, 5, 6, 7.7]
 >>> import random
 >>> collection_arg = random.sample(range(-50, 50), 100)
 >>> bubble_sort_iterative(collection_arg) == sorted(collection_arg)
 True
 >>> import string
 >>> collection_arg = random.choices(string.ascii_letters + string.digits, k=100)
 >>> bubble_sort_iterative(collection_arg) == sorted(collection_arg)
 True
 """
length=len(collection)
foriinreversed(range(length)):
swapped=False
forjinrange(i):
ifcollection[j] >collection[j+1]:
swapped=True
collection[j], collection[j+1] =collection[j+1], collection[j]
ifnotswapped:
break# Stop iteration if the collection is sorted.
returncollection


defbubble_sort_recursive(collection: list[Any]) ->list[Any]:
"""It is similar iterative bubble sort but recursive.

 :param collection: mutable ordered sequence of elements
 :return: the same list in ascending order

 Examples:
 >>> bubble_sort_recursive([0, 5, 2, 3, 2])
 [0, 2, 2, 3, 5]
 >>> bubble_sort_iterative([])
 []
 >>> bubble_sort_recursive([-2, -45, -5])
 [-45, -5, -2]
 >>> bubble_sort_recursive([-23, 0, 6, -4, 34])
 [-23, -4, 0, 6, 34]
 >>> bubble_sort_recursive([0, 5, 2, 3, 2]) == sorted([0, 5, 2, 3, 2])
 True
 >>> bubble_sort_recursive([]) == sorted([])
 True
 >>> bubble_sort_recursive([-2, -45, -5]) == sorted([-2, -45, -5])
 True
 >>> bubble_sort_recursive([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34])
 True
 >>> bubble_sort_recursive(['d', 'a', 'b', 'e']) == sorted(['d', 'a', 'b', 'e'])
 True
 >>> bubble_sort_recursive(['z', 'a', 'y', 'b', 'x', 'c'])
 ['a', 'b', 'c', 'x', 'y', 'z']
 >>> bubble_sort_recursive([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6])
 [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7]
 >>> bubble_sort_recursive([1, 3.3, 5, 7.7, 2, 4.4, 6])
 [1, 2, 3.3, 4.4, 5, 6, 7.7]
 >>> bubble_sort_recursive(['a', 'Z', 'B', 'C', 'A', 'c'])
 ['A', 'B', 'C', 'Z', 'a', 'c']
 >>> import random
 >>> collection_arg = random.sample(range(-50, 50), 100)
 >>> bubble_sort_recursive(collection_arg) == sorted(collection_arg)
 True
 >>> import string
 >>> collection_arg = random.choices(string.ascii_letters + string.digits, k=100)
 >>> bubble_sort_recursive(collection_arg) == sorted(collection_arg)
 True
 """
length=len(collection)
swapped=False
foriinrange(length-1):
ifcollection[i] >collection[i+1]:
collection[i], collection[i+1] =collection[i+1], collection[i]
swapped=True

returncollectionifnotswappedelsebubble_sort_recursive(collection)


if__name__=="__main__":
importdoctest
fromrandomimportsample
fromtimeitimporttimeit

doctest.testmod()

# Benchmark: Iterative seems slightly faster than recursive.
num_runs=10_000
unsorted=sample(range(-50, 50), 100)
timer_iterative=timeit(
"bubble_sort_iterative(unsorted[:])", globals=globals(), number=num_runs
 )
print("\nIterative bubble sort:")
print(*bubble_sort_iterative(unsorted), sep=",")
print(f"Processing time (iterative): {timer_iterative:.5f}s for {num_runs:,} runs")

unsorted=sample(range(-50, 50), 100)
timer_recursive=timeit(
"bubble_sort_recursive(unsorted[:])", globals=globals(), number=num_runs
 )
print("\nRecursive bubble sort:")
print(*bubble_sort_recursive(unsorted), sep=",")
print(f"Processing time (recursive): {timer_recursive:.5f}s for {num_runs:,} runs")