Saltar para o conteúdo

Counting sort: diferenças entre revisões

Counting sort (editar)

Revisão das 21h17min de 2 de dezembro de 2016

2 075 bytes removidos ,  21h17min de 2 de dezembro de 2016
m
A Wikipédia não é um repositório de códigos
(ajeitando o counting)
m (A Wikipédia não é um repositório de códigos)
</syntaxhighlight>
 
=== Código em JAVAJava ===
<syntaxhighlight lang="java" line="1">
public void CountingSort(Integer[] v) {
</syntaxhighlight>
 
{{Portal3|Tecnologias de informação}}
<u><big>'''Variação: ordenar números negativos'''</big></u>
 
Apesar do Counting Sort ordenar apenas números inteiros. Pode-se também variá-lo para que ele ordene também números negativos.
 
Agora, na implementação, é preciso achar também o menor elemento do array. Assim, fazendo ''n = maior - menor + 1'' temos o intervalo que os elementos do array estão inseridos. Em seguida, criamos o array auxiliar de tamanho ''n'' (maior - menor + 1). Segue-se a implementação de forma praticamente igual a do Counting Sort para os inteiros, exceto pelo fato de decrementar o valor do menor ao invés de 1 na alocação dos elementos do array recebido para o array auxiliar. Assim, os elementos são adicionados em posições válidas e de forma ordenada. Exemplo: '''Counting Sort''' -  c[v[i] -1] += 1; '''Counting Sort para Negativos''' - c[v[i] -menor] += 1.
 
Abaixo, segue-se a implementação da variação em JAVA.<syntaxhighlight lang="java" line="1">
public static void CountingNegativo(Integer[] v) {
// acha maior
Integer maior = v[0];
for (int i = 1; i < v.length; i++) {
if (v[i] > maior) {
maior = v[i];
}
}
// acha menor
Integer menor = v[0];
for (int i = 0; i < v.length; i++) {
if (v[i] < menor) {
menor = v[i];
}
}
int n = maior - menor + 1;
int[] c = new int[n];
 
// frequencia
for (int i = 0; i < v.length; i++) {
c[v[i] -menor] += 1;
}
// cumulativa
for (int i = 1; i < c.length; i++) {
c[i] += c[i-1];
}
Integer[] b = new Integer[v.length];
for (int i = 0; i < b.length; i++) {
b[c[v[i] -menor] -1] = v[i];
c[v[i] -menor]--;
}
for (int i = 0; i < b.length; i++) {
v[i] = b[i];
}
}
</syntaxhighlight><ref>{{Citar web|url=http://stackoverflow.com/questions/11001797/using-counting-sort-on-negative-values|titulo=Using Counting Sort on Negative values?|acessodata=2016-12-02|obra=stackoverflow.com}}</ref>{{Portal3|Tecnologias de informação}}
 
[[Categoria:Algoritmos de ordenação]]
Obtida de "https://pt.wikipedia.org/wiki/Especial:MobileDiff/47372609"