Sleep sort

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 $O(n)$ (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 é $n+nx$, onde $x$ é o maior número da lista de elementos, resultando na complexidade $O(n^{2})$ (com n ≥ x). No algoritmo original a complexidade é a mesma, embora o tempo de execução seja $n+nxt$, onde $t$ é 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 $O(n)$ em $n$ processadores, resultando em $O(n^{2})$.

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

• «Neal Gafter's blog: Comentário sobre uma entrevista de Jim Davis a um candidato que propôs o Sleep sort»