Stalin Sort

Stalin Sort – сортировка навылет, один из алгоритмов сортировки с потерей данных.
Алгоритм очень производительный и эффективный, временная сложность O(n).

Работает следующим образом:

1. Проходим циклом по массиву, сравнивая текущий элемент со следующим
2. Если следующий элемент меньше текущего, то удаляем его
3. В итоге получаем отсортированный массив за O(n)

Пример вывода работы алгоритма:

Numbers: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Код на Питоне 3:

numbers = [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag.append(element)
        del numbers[i]
    else:
        maximal = element        
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Из недостатков можно отметить потерю данных, но если двигаться к утопичному, идеальному, отсортированному списку за O(n), то как иначе?

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/stalinSort

Источники

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk