Sleep sort
Este artigo ou secção necessita de expansão. |
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
editarUma 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
editarMuita 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
editarO 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.