Algoritmo de classificação por contagem

Neste tutorial, você aprenderá como funciona a classificação por contagem. Além disso, você encontrará exemplos funcionais de classificação por contagem em C, C ++, Java e Python.

A classificação por contagem é um algoritmo de classificação que classifica os elementos de uma matriz contando o número de ocorrências de cada elemento exclusivo na matriz. A contagem é armazenada em uma matriz auxiliar e a classificação é feita mapeando a contagem como um índice da matriz auxiliar.

Como funciona a classificação por contagem?

Descubra o elemento máximo (que seja max) do array fornecido. Dada matriz
Inicialize uma matriz de comprimento max+1com todos os elementos 0. Esta matriz é usada para armazenar a contagem dos elementos na matriz. Matriz de contagem
Armazene a contagem de cada elemento em seu respectivo índice na countmatriz.
Por exemplo: se a contagem do elemento 3 for 2, então, 2 é armazenado na 3ª posição da matriz de contagem. Se o elemento "5" não estiver presente na matriz, então 0 é armazenado na 5ª posição. Contagem de cada elemento armazenado
Armazene a soma cumulativa dos elementos da matriz de contagem. Isso ajuda a colocar os elementos no índice correto da matriz classificada. Contagem cumulativa
Encontre o índice de cada elemento da matriz original na matriz de contagem. Isso dá a contagem cumulativa. Coloque o elemento no índice calculado conforme mostrado na figura abaixo. Classificação de contagem
Depois de colocar cada elemento em sua posição correta, diminua sua contagem em um.

Algoritmo de classificação por contagem

 countSort (array, size) max <- encontra o maior elemento no array inicializa o array de contagem com todos os zeros para j <- 0 para size encontra o contador total de cada elemento único e armazena a contagem no jº índice no array de contagem para i <- 1 para max encontre a soma cumulativa e armazene-a na própria matriz de contagem para j <- tamanho reduzido para 1 restaure os elementos para a matriz diminua a contagem de cada elemento restaurado em 1

Exemplos de Python, Java e C / C ++

Python Java C C ++

 # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)

 // Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )

 // Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )

Complexidade

Complexidades de tempo:

Existem principalmente quatro loops principais. (Encontrar o maior valor pode ser feito fora da função.)

for-loop	tempo de contagem
1ª	O (máx)
2ª	O (tamanho)
3ª	O (máx)
4º	O (tamanho)

Complexidade geral = O(max)+O(size)+O(max)+O(size)=O(max+size)

Pior Caso Complexidade: O(n+k)
Melhor caso de complexidade: O(n+k)
Complexidade média do caso: O(n+k)

Em todos os casos acima, a complexidade é a mesma porque não importa como os elementos são colocados no array, o algoritmo passa por n+ktempos.

Não há comparação entre nenhum elemento, por isso é melhor do que as técnicas de classificação baseadas em comparação. Mas, é ruim se os inteiros forem muito grandes porque o array desse tamanho deve ser feito.

Complexidade do espaço:

A complexidade do espaço da contagem de classificação é O(max). Quanto maior a gama de elementos, maior é a complexidade do espaço.