-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathbubble_sort.py
More file actions
40 lines (31 loc) · 895 Bytes
/
bubble_sort.py
File metadata and controls
40 lines (31 loc) · 895 Bytes
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
"""
Bubble Sort
Bubble sort repeatedly steps through the list, compares adjacent elements
and swaps them if they are in the wrong order.
Reference: https://en.wikipedia.org/wiki/Bubble_sort
Complexity:
Time: O(n) best / O(n^2) average / O(n^2) worst
Space: O(1)
"""
from __future__ import annotations
def bubble_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using bubble sort.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> bubble_sort([3, 1, 2])
[1, 2, 3]
"""
n = len(array)
swapped = True
passes = 0
while swapped:
swapped = False
for i in range(1, n - passes):
if array[i - 1] > array[i]:
array[i - 1], array[i] = array[i], array[i - 1]
swapped = True
passes += 1
return array