Além dos métodos de ordenação interna vistos anteriormente, ainda existem outros que devem ser ressaltados. Normalmente, são melhores para conjuntos específicos de dados.
Ordenação digital: é adequada para conjuntos específicos de dados, como por exemplo CEP, porque tem o mesmo número de dígitos e seguem uma distribuição uniforme. Numa central de correios, por exemplo, as cartas poderiam ser separadas primeiro pelo primeiro dígito do CEP, e dentro dessa separação, pelo segundo dígito e assim por diante. Alguns algoritmos: radixsort, bucketsort.
Counting sort: ordenar um conjunto de N letras:
Contar as frequências de cada letra usando a chave como índice
Calcular a frequência acumulada
Ordenar no array temporário
Copiar no array original
Esse eu nem entendi muito bem, admito.
Ordenação parcial: ordenar parcialmente é pegar apenas os k primeiros registros de um conjunto de tamanho n em ordem. Mas esses k primeiros são ordenados de acordo com o total, só que depois deles o resto pode ficar tudo desordenado que não tem problema, a gente só queria os primeiros k mesmo.
Ordenação externa: a ordenação externa é efetuada quando o conjunto a ser ordenado não cabe na memória interna. São muito difíceis e exigem cuidado, pois o acesso a dados na memória externa é extremamente custoso e é apenas sequencial. Portanto, a complexidade é analisada de acordo com o número de transferências de dados entre memória externa ou secundária e a interna. Isso faz com que os métodos de ordenação externa variem de acordo com a tecnologia atual.
O método mais eficiente é a ordenação por intercalação. O algoritmo pega blocos de dados na memória externa, os ordena na memória interna e intercala esses blocos, fazendo várias passadas pelo arquivo. Eles são cada vez maiores, até que todo o arquivo esteja ordenado. To com preguiça de descrever o método das fitas, porque exige um exemplo. Caso um dia alguém precise, basta perguntar.
Nenhum comentário:
Postar um comentário