O Sleep sort é um algoritmo de ordenação de autoria desconhecida divulgado em diversos fóruns e comunidades na Internet. Sua execução baseia na criação de diversos sub-processos adormecidos de modo que estes sejam acordados na ordem apropriada.
Funcionamento Uma das versões do algoritmo (escrito em bash shell script) é descrita a seguir:
# !/bin/bash
function f() { sleep "$1" echo "$1" }
while [ -n "$1" ] do f "$1" & shift done
wait
Nessa implementação uma função é responsável por imprimir o parâmetro passado --- que obrigatóriamente deve ser numérico e positivo --- após aguardar a mesma quantidade de tempo.
Problemas Muita discussão ocorre sobre a complexidade desse algoritmo. Embora alguns acreditem que a complexidade seja (considerando que cada elemento é visitado uma única vez), esse algoritmo abusa de rotinas complexas de alto nível que torna sua complexidade mais difícil de ser estabelecida. No algoritmo verifica-se a utilização da função sleep, que adormece um processo gerando ciclos do processador ou aguardando uma condição ser atingida; e do fork, que gera um subprocesso.
Serializando as funções sleep e fork, pode-se considerar o seguinte código como equivalente:
lista = [ 5, 3, 6, 3, 6, 3, 1, 4, 7 ]
listaFork = [ (i,i) for i in lista ] maxSleep = max(lista) lista = []
for _ in range(maxSleep): for i in range(len(listaFork)): j,k = listaFork[i] k = k - 1 if not k: lista.append(j) listaFork[i] = j,k
print(lista)
Baseando neste algoritmo (escrito em Python) o tempo de execução é , onde é o maior número da lista de elementos, resultando na complexidade (com n ≥ x). No algoritmo original a complexidade é a mesma, embora o tempo de execução seja , onde é a constante de tempo (um segundo neste caso, devido ao funcionamento da função sleep). Outro possível modo de identificar a complexidade do algoritmo é verificar que ele é executado em tempo em processadores, resultando em .
Embora teoricamente correto, esse algoritmo não deve ser considerado utilizável em implementações reais por apresentar diversos problemas. O principal deles reside na condição de corrida que é inerente à sua implementação. Sem sombra de dúvidas, se os valores estiverem muito próximos um do outro, o algoritmo não é capaz de ordenar a lista satisfatóriamente, além disso, a premissa de que os dados sejam sempre positivos é uma premissa forte pois implica que o intervalo em que os dados estão compreendidos seja uma informação conhecida.
Inspiração
O mecanismo subjacente do Sleep sort se assemelha ao algoritmo Counting sort. Este, também de complexidade O(n), instancia um array do tamanho do maior elemento e então coloca cada item na sua respectiva posição no array. O array resultante estará naturalmente ordenado.
Ligações externas
Categoria:Algoritmos de ordenação