Sleep sort

Origem: Wikipédia, a enciclopédia livre.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.

Referências

Ligações externas[editar | editar código-fonte]