Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar o Stalin Sort no Python?

0 votos
11 visitas
perguntada Mai 21 em Programação Computacional por Stuart Mill (1,404 pontos)  

O Stalin Sort é um algoritmo de ordenação em que os elementos fora de ordem da lista são removidos, e uma lista ordenada é retornada. Qual a eficiência computacional desse algoritmo e qual seria uma implementação simples no Python?

Compartilhe

1 Resposta

0 votos
respondida Mai 21 por Stuart Mill (1,404 pontos)  
editado Jun 2 por Stuart Mill

A performance é sempre da ordem de \(O(n)\), já que o array só é percorrido uma vez. Uma implementação simples (mas não eficiente) no Python seria algo como:

def stalin_sort(lst:list)->list:
    to_keep = []
    last_ordered = lst[0]
    for number in lst:
        if number >= last_ordered:
            last_ordered = number
            to_keep.append(number)
    return to_keep

Testando:

from random import randint

testlist = [randint(-10, 10) for i in range(100)]
baseline = sorted(testlist)
stalin = stalin_sort(testlist)

Referências

...