Como usar a classificação de distribuição (classificação radix, etc) para classificar strings?

Question

Eu sei como usar a classificação radix para classificar números inteiros.

Mas como usá-lo para classificar strings?ou números flutuantes?

Answer 1

A classificação de raiz ou qualquer outra classificação de distribuição pode ser usada para classificar números de ponto flutuante se você ignorar algumas peculiaridades deles, como infinito, valores que não são números e duas representações diferentes de zero. IEEE 754-2008 números de ponto flutuante têm representações binárias, compatíveis na ordem de classificação com números inteiros.Então, se você excluir não-números e reinterpretar float ou double como int32 ou int64, você pode aplicar diretamente qualquer classificação de distribuição a eles. Editar: Os números de ponto flutuante negativo precisam de tratamento especial (conforme apontado por AShelly), porque sua ordem de classificação é oposta à ordem de classificação dos números inteiros.

Com strings, é mais difícil devido ao seu comprimento variável.Outro tipo de classificação de distribuição (classificação de intervalo) pode ser usado e é frequentemente usado para strings.Vários caracteres iniciais da string são usados ​​para indexação de bucket e, em seguida, qualquer classificação comparativa é usada para classificar strings dentro dos buckets.

Se todas as cordas tiverem comprimento quase igual e/ou alguma técnica for usada para amplificar as diferenças entre as cordas (como descrito no capítulo 6 do "RÁPIDO:Pesquisa rápida de árvore sensível à arquitetura em CPUs e GPUs modernas"), então radix sort também pode ser usado:divida a string em grupos de caracteres (ou melhor, em grupos de bits) de igual comprimento, reinterprete esses grupos como inteiros e continue como se fosse uma classificação de base para inteiros.

Editar: Todos os tipos de classificação de distribuição funcionam corretamente apenas para strings ASCII.Outras codificações de string podem exigir uma ordem de classificação diferente ou podem depender do parâmetro "agrupar" do código do idioma.

Answer 2

Sim, é possível.

ver Classificação de Radix, classificando um bloat Data para flutuadores.Ele usa o fato de que flutuarem para os tipos inteiros comparados corretamente (uma vez que os negativos sejam corrigidos).Ver Este artigo Para detalhes

Para strings, você pode resolver o problema de comprimento variável fazendo uma classificação de RADIX MSD e garantindo que pare de descer quando você encontra nulls.Veja Classe Radix implementado em C ++ para string .