forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbogo_sort.py
More file actions
41 lines (29 loc) · 900 Bytes
/
bogo_sort.py
File metadata and controls
41 lines (29 loc) · 900 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
41
"""
Bogo Sort
Bogo sort repeatedly shuffles the array at random until it happens to be
sorted. It is extremely inefficient and used only for educational purposes.
Reference: https://en.wikipedia.org/wiki/Bogosort
Complexity:
Time: O(n) best / O(n * n!) average / O(infinity) worst
Space: O(1)
"""
from __future__ import annotations
import random
def bogo_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using bogo sort.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> bogo_sort([3, 1, 2])
[1, 2, 3]
"""
while not _is_sorted(array):
random.shuffle(array)
return array
def _is_sorted(array: list[int]) -> bool:
"""Return True if *array* is in non-decreasing order."""
return all(
array[i] <= array[i + 1] for i in range(len(array) - 1)
)