Counting sort: diferenças entre revisões

88 bytes adicionados ,  19h03min de 2 de dezembro de 2016
m
(Acréscimo do código em Java.)
m (+correções semiautomáticas (v0.50/3.1.38))
{{Sem-fontes|data=agosto de 2012| angola=| arte=| Brasil=| ciência=sim| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}}
{{Info/Algoritmo
|classe = [[Algoritmo de ordenação]]
|imagem =
|estrutura = [[Array]], [[Lista ligada|Listas ligadas]]
|data =
|pior_caso = <math>O(n + k)</math>
|melhor_caso = <math>O(n + k)</math>
|caso_medio = <math>O(n + k)</math>
|complexidade =
|otimo =
|estabilidade =
}}
 
'''Counting sort''' é um [[algoritmo de ordenação]] estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1.
 
== Implementações ==
# Cria cnt[M+1] e b[max N]
 
# Inicializa todas as posições de cnt a 0.
#Cria cnt[M+1] e b[max N]
# Percorre o vector a e, para cada posição i de a faz cnt[a[i]-1]++ o que faz com que, no final, cada posição i de cnt contem o nº de vezes que a chave i-1 aparece em a.
#Inicializa todas as posições de cnt a 0.
#Percorre oAcumula vectorem acada e,elemento parade cadacnt posiçãoo ielemento desomado aao elemento fazanterior: cnt[a[i]-1]++ oindica que faz com que, no final, cadaa posição iordenada dedo cnt contem oprimeiro elemento de vezes que a chave i-1 aparece em a.
# Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
#Acumula em cada elemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
# Copia b para a.
#Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
# Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências.
#Copia b para a.
#Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências.
Esta implementação tem a desvantagem de precisar de vectores auxiliares.
O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.
 
=== Código em [[C++]] ===
<sourcesyntaxhighlight lang="c">
template<class T>
std::vector<T> counting_sort( const std::vector<T> &op )
return ordenado;
}
</syntaxhighlight>
</source>
 
=== Código em C ===
<sourcesyntaxhighlight lang="c">
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <ctype.h>
 
# define MAX 100001
 
struct data
{
int number;
char key[100];
}DataBase[MAX], VectorSort[MAX];
 
int main (void)
{
int i = 0;
 
while(scanf("%d%s",&DataBase[size].number,DataBase[size].key) >= 1)
size++;
int aux[2] = {0,0};
for(i = 0; i <= size;i++)
aux[DataBase[i].number]++;
 
int aux[12] += aux[{0],0};
for(i = 0; i <= size;i++)
aux[DataBase[i].number]++;
for(i = size - 1;i >= 0;i--)
VectorSort[--aux[DataBase[i].number]] = DataBase[i];
 
int aux[21] += {0,aux[0}];
for(i = 0; i < size;i++)
printf("Number: %d --- Key: %s\n",VectorSort[i].number,VectorSort[i].key);
 
for(i = size - 1;i >= 0;i--)
return 0;
VectorSort[--aux[DataBase[i].number]] = DataBase[i];
 
for(i = 0; i < size;i++)
printf("Number: %d --- Key: %s\n",VectorSort[i].number,VectorSort[i].key);
 
return 0;
}
</source>'''Código em JAVA'''<syntaxhighlight lang="java" line="1">
 
=== Código em JAVA ===
<syntaxhighlight lang="java" line="1">
public static void CountingSort(int[] a) {
 
int maior = v[0];
for (int i = 1; i < v.length; i++) {
if (v[i] > maior) {
maior = v[i];
}
}
 
// frequencia
int[] c = new int[maior];
for (int i = 0; i < v.length; i++) {
c[v[i] -1] += 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] -1] -1] = v[i];
c[v[i] -1]--;
}
 
// passando os elementos do array ordenado para o array recebido no parâmetro
for (int i = 0; i < b.length; i++) {
v[i] = b[i];
</syntaxhighlight>
 
{{Portal3|Tecnologias de informação}}
 
[[Categoria:Algoritmos de ordenação]]