Neste artigo, discutiremos o algoritmo de classificação de contagem. A classificação por contagem é uma técnica de classificação baseada nas chaves entre intervalos específicos. Em entrevistas técnicas ou de codificação para engenheiros de software, algoritmos de classificação são amplamente solicitados. Então, é importante discutir o tema.
Esta técnica de classificação não realiza classificação comparando elementos. Ele realiza a classificação contando objetos com valores-chave distintos, como hash. Depois disso, ele realiza algumas operações aritméticas para calcular a posição do índice de cada objeto na sequência de saída. A classificação por contagem não é usada como um algoritmo de classificação de uso geral.
A classificação por contagem é eficaz quando o intervalo não é maior que o número de objetos a serem classificados. Ele pode ser usado para classificar os valores de entrada negativos.
Agora, vamos ver o algoritmo de classificação de contagem.
Algoritmo
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Trabalho de algoritmo de classificação de contagem
Agora, vamos ver o funcionamento do algoritmo de contagem e ordenação.
Para entender o funcionamento do algoritmo de classificação por contagem, vamos pegar um array não classificado. Será mais fácil entender a classificação da contagem por meio de um exemplo.
Deixe os elementos do array serem -
como obter emojis de maçã no Android
1. Encontre o elemento máximo do array fornecido. Deixar máx. seja o elemento máximo.
2. Agora, inicialize o array de comprimento máximo + 1 tendo todos os 0 elementos. Este array será usado para armazenar a contagem dos elementos no array fornecido.
3. Agora, temos que armazenar a contagem de cada elemento do array em seu índice correspondente no array de contagem.
A contagem de um elemento será armazenada como - Suponha que o elemento '4' da matriz apareça duas vezes, então a contagem do elemento 4 é 2. Portanto, 2 é armazenado no 4ºposição da matriz de contagem. Se algum elemento não estiver presente no array, coloque 0, ou seja, suponha que o elemento '3' não esteja presente no array, então, 0 será armazenado em 3terceiroposição.
Agora, armazene a soma cumulativa de contar elementos da matriz. Ajudará a colocar os elementos no índice correto da matriz classificada.
Da mesma forma, a contagem cumulativa da matriz de contagem é -
4. Agora encontre o índice de cada elemento do array original
Após colocar o elemento em seu lugar, diminua sua contagem em um. Antes de colocar o elemento 2, sua contagem era 2, mas depois de colocá-lo na posição correta, a nova contagem para o elemento 2 é 1.
Da mesma forma, após a classificação, os elementos da matriz são -
Agora, o array está completamente classificado.
Contando a complexidade da classificação
Agora, vamos ver a complexidade de tempo da classificação de contagem no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial da classificação de contagem.
1. Complexidade de tempo
| Caso | Tempo | Complexidade |
|---|---|---|
| Melhor caso | O (n + k) | |
| Caso médio | O (n + k) | |
| Pior caso | O (n + k) |
Em todos os casos acima, a complexidade de tempo da classificação de contagem é a mesma. Isso ocorre porque o algoritmo passa por n + k vezes, independentemente de como os elementos são colocados na matriz.
A classificação por contagem é melhor do que as técnicas de classificação baseadas em comparação porque não há comparação entre os elementos na classificação por contagem. Mas, quando os números inteiros são muito grandes, a classificação da contagem é ruim porque é necessário criar matrizes desse tamanho.
2. Complexidade Espacial
| Complexidade Espacial | O(max) |
| Estábulo | SIM |
- A complexidade espacial da classificação por contagem é O (máx). Quanto maior for a gama de elementos, maior será a complexidade do espaço.
Implementação de classificação de contagem
Agora, vamos ver os programas de classificação de contagem em diferentes linguagens de programação.
Programa: Escreva um programa para implementar a classificação por contagem em linguagem C.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Saída
java gera número aleatório
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.
Este artigo não se limitou apenas ao algoritmo. Também discutimos a complexidade, o funcionamento e a implementação da classificação de contagem em diferentes linguagens de programação.