92 011
edições
Counting sort (editar)
Revisão das 19h03min de 2 de dezembro de 2016
, 19h03min de 2 de dezembro de 2016+correções semiautomáticas (v0.50/3.1.38)
(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=|
{{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]▼
▲#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.
#
# Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[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++]] ===
<
template<class T>
std::vector<T> counting_sort( const std::vector<T> &op )
return ordenado;
}
</syntaxhighlight>
=== Código em 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)
int aux[2] = {0,0}; ▼
for(i = 0; i <= size;i++)▼
aux[DataBase[i].number]++;▼
int aux[
▲ for(i = 0; i <= size;i++)
for(i = size - 1;i >= 0;i--)▼
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);▼
▲ for(i = size - 1;i >= 0;i--)
return 0;▼
▲ for(i = 0; i < size;i++)
▲ return 0;
}
</
=== 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) {
}
}
// 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++) {
</syntaxhighlight>
{{Portal3|Tecnologias de informação}}
[[Categoria:Algoritmos de ordenação]]
| |||