Classificação MSD vs LSD Radix

Question

Eu li o seguinte em CRLS:

Não entendo o texto em amarelo.Por que radix sort não funciona tão bem se classificarmos pelo dígito mais significativo?A que "pilhas de cartas" extras ele se refere?

Talvez eu não consiga seguir o exemplo com cartas, e um exemplo com números reais seria melhor.

---

Caso ajude, classificando ingenuamente pelo MSD parece não funcionar, mesmo que todos os valores sejam números de d dígitos:

Input   (1)   (2)   (3)
        *      *      *
 321    132   321   321
 522    321   426   522
 132    426   522   132
 426    522   132   426

onde (i) é o resultado da classificação da coluna anterior pelo i-ésimo dígito mais alto.

Answer 1

Funcionaria, o único problema é que geraria muitas pilhas extras para os resultados intermediários que são difíceis de rastrear.

se o algoritmo de classificação classifica o $d$-números de dígitos começando com seu dígito mais significativo, ele criaria 10 pilhas primeiro (uma pilha para os números começando com 0, outra para aqueles começando com 1 e assim por diante) e então classificaria cada pilha recursivamente conforme explicado no livro.

O problema é que para ordenar a pilha de números começando com 0 o algoritmo precisa criar mais dez pilhas (uma para os números começando com 00, a segunda para os números começando com 01 e assim por diante, a última pilha é para os números começando com 00). com 09).

Assim criamos 19 pilhas até agora.Para ordenar a pilha de números começando com 00, precisamos criar mais 10 pilhas.Se esse processo continuar até o $d$ dígitos são classificados, você pode imaginar que um grande número de pilhas é criado (quantas?).

Estas são as pilhas extras às quais o livro se referia.

Se você usar o LSD radix sort, não será necessário dividir os números em pilhas.Você pode simplesmente classificar a pilha de entrada pelo último dígito, depois a mesma pilha pelo penúltimo dígito e assim por diante, depois $d$ etapas você terminará com o resultado esperado.

A intuição é o seguinte:deixar $d$ ser $2$ e deixar $83$, $19$ e $17$ seja a entrada.A primeira etapa na classificação de base do MSD será colocada $17$ e $19$ antes $83$.Então, se você classificar a mesma pilha inteira pelo segundo dígito, você terminará com $83$ antes $17$ o que está errado.Você precisa dividir a pilha porque tem que “lembrar” da ordenação anterior feita pelo algoritmo, que é mais “importante”.Por outro lado, a primeira etapa do LSD radix sort colocará $83$ antes $17$, então $19$.Se você pegar a pilha inteira e classificá-la pelo primeiro dígito, você obterá $17$, $19$, $83$ qual é correto.Você não precisa dividir a pilha porque a etapa atual do algoritmo é mais "importante" das anteriores e é permitido "bagunçar" a ordenação anterior de qualquer forma (por exemplo, colocando $83$ depois $17$ e $19$).Isso funcionaria desde que o algoritmo de classificação usado para cada dígito fosse estável.