logo

TechCodeview

Tri par comptage – Tutoriels sur les structures de données et les algorithmes

Qu’est-ce que le tri par comptage ?

Tri par comptage est un non basé sur une comparaison algorithme de tri qui fonctionne bien lorsque la plage de valeurs d'entrée est limitée. Il est particulièrement efficace lorsque la plage de valeurs d’entrée est petite par rapport au nombre d’éléments à trier. L'idée de base derrière Tri par comptage c'est compter le fréquence de chaque élément distinct dans le tableau d'entrée et utiliser ces informations pour placer les éléments dans leurs positions triées correctes.

Comment fonctionne l'algorithme de tri par comptage ?

Étape 1 :



  • Découvrez le maximum élément du tableau donné.

Trouver l'élément maximum dans inputArray[]

Étape 2:

  • Initialiser un compteTableau[] de longueur maximum+1 avec tous les éléments comme 0 . Ce tableau sera utilisé pour stocker les occurrences des éléments du tableau d'entrée.

Initialiser countArray[]



Étape 3:

  • Dans le compteTableau[] , stockez le nombre de chaque élément unique du tableau d'entrée à leurs indices respectifs.
  • Par exemple: Le nombre d'éléments 2 dans le tableau d'entrée est 2. Alors, stockez 2 à l'index 2 dans le compteTableau[] . De même, le nombre d'éléments 5 dans le tableau d'entrée est 1 , donc stocker 1 à l'index 5 dans le compteTableau[] .

Conserver le nombre de chaque élément dans countArray[]

Étape 4:



  • Conservez le somme cumulée ou somme de préfixe des éléments du compteTableau[] en faisant countArray[i] = countArray[i – 1] + countArray[i]. Cela aidera à placer les éléments du tableau d'entrée au bon index dans le tableau de sortie.

Stocker la somme cumulée dans countArray[]

Étape 5 :

  • Itérer à partir de la fin du tableau d'entrée et parce que parcourir le tableau d'entrée à partir de la fin préserve l'ordre des éléments égaux, ce qui finit par rendre cet algorithme de tri écurie .
  • Mise à jour OutputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Mettez également à jour countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Étape 6 : Pour je = 6 ,

pour les boucles java

Mise à jour outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Mettez également à jour countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Placer inputArray[6] à la position correcte dans outputArray[]

Étape 7 : Pour i = 5 ,

Mise à jour outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Mettez également à jour countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Placer inputArray[5] à la position correcte dans outputArray[]

Étape 8 : Pour je = 4 ,

Mise à jour outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Mettez également à jour countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Placer inputArray[4] à la position correcte dans outputArray[]

Étape 9 : Pour je = 3 ,

Mise à jour OutputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Mettez également à jour countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Placer inputArray[3] à la position correcte dans outputArray[]

Étape 10 : Pour je = 2 ,

Mise à jour outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Mettez également à jour countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Placer inputArray[2] à la position correcte dans outputArray[]

Étape 11 : Pour je = 1 ,

Mise à jour OutputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Mettez également à jour countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Placer inputArray[1] à la position correcte dans outputArray[]

Étape 12 : Pour je = 0,

Mise à jour OutputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Mettez également à jour countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Placer inputArray[0] à la position correcte dans outputArray[]

Algorithme de tri par comptage :

  • Déclarer un tableau auxiliaire compteTableau[] de taille max(inputArray[])+1 et initialisez-le avec 0 .
  • Tableau de parcours tableau d'entrée[] et cartographier chaque élément de tableau d'entrée[] comme indice de compteTableau[] tableau, c'est-à-dire exécuter compteArray[inputArray[i]]++ pour 0 <= je .
  • Calculer la somme des préfixes à chaque index du tableau tableau d'entrée [].
  • Créer un tableau tableau de sortie[] de taille N .
  • Tableau de parcours tableau d'entrée[] depuis la fin et mise à jour OutputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Mettez également à jour countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Vous trouverez ci-dessous l'implémentation de l'algorithme ci-dessus :

Java




import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0 ; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return tableau de sortie ; } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[] outputArray = countSort(inputArray); pour (int i = 0; i System.out.print(outputArray[i] + ' '); } } }> 

>

>

C#




using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort(Liste<>int>>tableau d'entrée)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = nouvelle liste (nouveau int[M + 1]); // Mappage de chaque élément de inputArray[] en tant qu'index // du tableau countArray[] pour (int i = 0; i countArray[inputArray[i]]++; // Calcul de la somme des préfixes à chaque index // du tableau countArray [] pour (int je = 1; je<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List OutputArray = nouvelle liste (nouveau int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return tableau de sortie ; } // Code du pilote static void Main() { // Liste du tableau d'entrée inputArray = nouvelle liste { 4, 3, 12, 1, 5, 5, 3, 9 } ; // Liste du tableau de sortie OutputArray = CountSort(inputArray); pour (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }> 

>

>

Javascript




function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0 ; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return tableau de sortie ; } // Code du pilote const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Tri du tableau d'entrée const outputArray = countSort(inputArray); // Impression du tableau trié console.log(outputArray.join(' ')); //Ce code est contribué par Utkarsh>

un exemple de système d'exploitation open source est 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vecteur<>int>>& tableau d'entrée)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector countArray(M + 1, 0); // Mappage de chaque élément de inputArray[] en tant qu'index // du tableau countArray[] pour (int i = 0; i countArray[inputArray[i]]++; // Calcul de la somme des préfixes à chaque index // du tableau countArray [] pour (int je = 1; je<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector tableau de sortie (N); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return tableau de sortie ; } // Code du pilote int main() { // Vecteur de tableau d'entrée tableau d'entrée = { 4, 3, 12, 1, 5, 5, 3, 9 } ; // Vecteur de tableau de sortie OutputArray = countSort(inputArray); pour (int i = 0; je cout<< outputArray[i] << ' '; return 0; }> 

>

>

Python3




def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)> 

>

>

Sortir 

1 3 3 4 5 5 9 12>

Analyse de la complexité du tri par comptage :

  • Complexité temporelle : O(N+M), où N et M sont la taille de tableau d'entrée[] et compteTableau[] respectivement.
    • Dans le pire des cas : O(N+M).
    • Cas moyen : O(N+M).
    • Meilleur des cas : O(N+M).
  • Espace auxiliaire : O(N+M), où N et M est l'espace occupé par tableau de sortie[] et compteTableau[] respectivement.

Avantage du tri par comptage :

  • Le tri par comptage est généralement plus rapide que tous les algorithmes de tri basés sur des comparaisons, tels que le tri par fusion et le tri rapide, si la plage d'entrée est de l'ordre du nombre d'entrées.
  • Le tri par comptage est facile à coder
  • Le tri par comptage est un algorithme stable .

Inconvénient du tri par comptage :

  • Le tri par comptage ne fonctionne pas sur les valeurs décimales.
  • Le tri par comptage est inefficace si la plage de valeurs à trier est très large.
  • Le tri par comptage n'est pas un Tri sur place algorithme, il utilise un espace supplémentaire pour trier les éléments du tableau.