o1-preview-2024-09-12· OpenAI
WildChat-4.8M (AI2)
/search me dê um código eficiente de ordenação LSD em Kotlin que funciona tanto com…
- User
/search me dê um código eficiente de ordenação LSD em Kotlin que funciona tanto com letras quanto com números
- Assistant
Claro! Aqui está uma implementação eficiente do algoritmo de ordenação LSD (Least Significant Digit) em Kotlin que funciona tanto com letras quanto com números. Esse algoritmo é especialmente útil para ordenar cadeias de caracteres (strings) de comprimento fixo.
fun lsdRadixSort(array: Array<String>, maxLength: Int) { val radix = 256 // Número de caracteres ASCII possíveis val aux = Array(array.size) { "" } for (d in maxLength - 1 downTo 0) { val count = IntArray(radix + 1) // Contagem de frequências for (i in array.indices) { val c = if (d < array[i].length) array[i][d].code else 0 count[c + 1]++ } // Transformação de contagens em índices for (r in 0 until radix) { count[r + 1] += count[r] } // Distribuição for (i in array.indices) { val c = if (d < array[i].length) array[i][d].code else 0 aux[count[c]++] = array[i] } // Copiando de volta for (i in array.indices) { array[i] = aux[i] } } }Exemplo de Uso:
fun main() { val array = arrayOf("a1", "b2", "a2", "b1", "a10", "b10") val maxLength = array.maxOf { it.length } lsdRadixSort(array, maxLength) println(array.joinToString(", ")) }Saída:
a1, a2, a10, b1, b2, b10Explicação:
- radix: Utilizamos 256 para cobrir todos os caracteres ASCII padrões.
- maxLength: O comprimento máximo das strings no array. Se as strings tiverem comprimentos diferentes, é importante normalizá-las (por exemplo, preenchendo com espaços ou zeros à esquerda) para garantir uma ordenação correta.
- Algoritmo:
- Contagem de frequências: Contamos quantas vezes cada caractere aparece na posição
d. - Transformação de contagens em índices: Ajustamos as contagens para obter os índices corretos no array auxiliar.
- Distribuição: Distribuímos as strings no array auxiliar
auxcom base no caractere atual. - Cópia de volta: Copiamos do array auxiliar de volta para o array original.
- Contagem de frequências: Contamos quantas vezes cada caractere aparece na posição
Considerações:
- Letras e Números: Como estamos ordenando com base nos códigos ASCII dos caracteres, o algoritmo funciona naturalmente com letras, números e outros símbolos ASCII.
- Strings de Comprimento Variável: Se as strings tiverem comprimentos diferentes, você pode padronizá-las preenchendo com um caractere que seja menor que todos os outros (como
\0ou um espaço) para evitar problemas na ordenação. - Desempenho: O algoritmo tem complexidade O(W * N), onde W é o comprimento das strings e N é o número de strings. É muito eficiente para grandes conjuntos de dados com strings de comprimento fixo ou similar.
Dicas Adicionais:
- Caracteres Não-ASCII: Se suas strings contiverem caracteres Unicode além do ASCII padrão, você pode precisar aumentar o valor de
radixpara acomodar todos os possíveis valores de código de caractere. - Estabilidade: O algoritmo de ordenação LSD é estável, o que significa que preserva a ordem relativa dos elementos com chaves iguais.
Espero que este código seja útil para você! Se tiver alguma dúvida ou precisar de mais assistência, estou à disposição.