48 lines
994 B
Python
48 lines
994 B
Python
|
"""
|
||
|
|
Stalin Sort algorithm: Removes elements that are out of order.
|
||
|
|
Elements that are not greater than or equal to the previous element are discarded.
|
||
|
|
Reference: https://medium.com/@kaweendra/the-ultimate-sorting-algorithm-6513d6968420
|
||
|
|
"""
|
||
|
|
|
||
|
|
|
||
|
|
def stalin_sort(sequence: list[int]) -> list[int]:
|
||
|
|
"""
|
||
|
|
Sorts a list using the Stalin sort algorithm.
|
||
|
|
|
||
|
|
>>> stalin_sort([4, 3, 5, 2, 1, 7])
|
||
|
|
[4, 5, 7]
|
||
|
|
|
||
|
|
>>> stalin_sort([1, 2, 3, 4])
|
||
|
|
[1, 2, 3, 4]
|
||
|
|
|
||
|
|
>>> stalin_sort([4, 5, 5, 2, 3])
|
||
|
|
[4, 5, 5]
|
||
|
|
|
||
|
|
>>> stalin_sort([6, 11, 12, 4, 1, 5])
|
||
|
|
[6, 11, 12]
|
||
|
|
|
||
|
|
>>> stalin_sort([5, 0, 4, 3])
|
||
|
|
[5]
|
||
|
|
|
||
|
|
>>> stalin_sort([5, 4, 3, 2, 1])
|
||
|
|
[5]
|
||
|
|
|
||
|
|
>>> stalin_sort([1, 2, 3, 4, 5])
|
||
|
|
[1, 2, 3, 4, 5]
|
||
|
|
|
||
|
|
>>> stalin_sort([1, 2, 8, 7, 6])
|
||
|
|
[1, 2, 8]
|
||
|
|
"""
|
||
|
|
result = [sequence[0]]
|
||
|
|
for element in sequence[1:]:
|
||
|
|
if element >= result[-1]:
|
||
|
|
result.append(element)
|
||
|
|
|
||
|
|
return result
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
import doctest
|
||
|
|
|
||
|
|
doctest.testmod()
|