TheAlgorithms-Python
56 строк · 1.4 Кб
1"""
2Gnome Sort Algorithm (A.K.A. Stupid Sort)
3
4This algorithm iterates over a list comparing an element with the previous one.
5If order is not respected, it swaps element backward until order is respected with
6previous element. It resumes the initial iteration from element new position.
7
8For doctests run following command:
9python3 -m doctest -v gnome_sort.py
10
11For manual testing run:
12python3 gnome_sort.py
13"""
14
15
16def gnome_sort(lst: list) -> list:
17"""
18Pure implementation of the gnome sort algorithm in Python
19
20Take some mutable ordered collection with heterogeneous comparable items inside as
21arguments, return the same collection ordered by ascending.
22
23Examples:
24>>> gnome_sort([0, 5, 3, 2, 2])
25[0, 2, 2, 3, 5]
26
27>>> gnome_sort([])
28[]
29
30>>> gnome_sort([-2, -5, -45])
31[-45, -5, -2]
32
33>>> "".join(gnome_sort(list(set("Gnomes are stupid!"))))
34' !Gadeimnoprstu'
35"""
36if len(lst) <= 1:
37return lst
38
39i = 1
40
41while i < len(lst):
42if lst[i - 1] <= lst[i]:
43i += 1
44else:
45lst[i - 1], lst[i] = lst[i], lst[i - 1]
46i -= 1
47if i == 0:
48i = 1
49
50return lst
51
52
53if __name__ == "__main__":
54user_input = input("Enter numbers separated by a comma:\n").strip()
55unsorted = [int(item) for item in user_input.split(",")]
56print(gnome_sort(unsorted))
57