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.
Contagem de aplicativos de classificação
A classificação por contagem é usada quando:
- existem números inteiros menores com múltiplas contagens.
- complexidade linear é a necessidade.
