Que vantagem o heapsort tem sobre o smoothsort?

8

A Wikipedia afirma que as vantagens do smoothsort sobre o heapsort é que, às vezes , chega mais perto do tempo O (n).

Agora eu estava imaginando que vantagem o heapsort tem sobre o smoothsort?

Ou, para reformular esta pergunta, o smoothsort é sempre uma escolha melhor que o heapsort (mesmo que a entrada ainda não esteja classificada em nenhum grau)?

ds.algorithms sorting Pacerier
fonte
Você comparou implementações? Talvez a diferença seja que smoothsort tem uma sobrecarga maior, tanto em termos de tempo de execução quanto de memória usada.
Dave Clarke
8
No heapsort, você pode construir o heap no tempo O (n), enquanto no smoothsort, leva tempo O (n log n) para construir o heap. Isso sugere (mas não implica) que o tempo para classificar entradas aleatórias pode ser mais longo para a classificação suave.
quer
@DaveClarke Quero dizer não na implementação (que pode variar), mas no próprio algoritmo
Pacerier
@PeterShor Tem certeza de que é necessário O (n log n) para criar a pilha no smoothsort? Isso parece ir direto ao argumento de que smoothsort é O (n) quando a entrada já está classificada?
Paul Wagland
1
@ PeterShor: Uma variante do smoothsort que usa uma lista binária inclinada, pois a floresta de montões pode ser empilhada em O (n) tempo. Para fazer isso, converta o comprimento da entrada em enviesado binário (O (log (n)). Os bits desse número indicam os tamanhos de heap na floresta. Finja que essa floresta já existe e ainda não possui a propriedade heap. Isso é semelhante a no heapsort, fingindo que você já possui um heap sem a propriedade heap. No entanto, mesmo com essa alteração, o smoothsort (usando o binário inclinado) é apenas mais rápido que o heapsort para 10% ou menos não classificado (usando inversões para não classificar).
precisa saber é o seguinte

Respostas:

10

Tendo acabado feito alguma leitura sobre os dois algoritmos, parece que heapsort não tem implícita O vantagem sobre smoothsort. Isso faz sentido quando você pensa que smoothsort é apenas um tipo especial de heapsort, usando um tipo especial de pilha.

A vantagem do heapsort é que ele é mais fácil de entender e muito melhor documentado. Existem muito poucas implementações publicamente disponíveis do smoothsort e muito pouca literatura sobre elas, no entanto, há muita literatura sobre o heapsort.

De fato, a única literatura acessível real é esse artigo de Keith Schwarz. É também a base do artigo da Wikipedia .

Paul Wagland
fonte