Compter la complexité de tri

Qu'est-ce que le rythme de comptage?

Le rythme de comptage est mieux illustré avec le tri des entiers. En C / C ++ et Java, les personnages sont des entiers et peuvent être triés dans la façon dont les entiers sont triés. Considérez la liste des entiers non triés suivants:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Cette liste est triée par ordre croissant. Il peut être donné (reçu par le programme de tri) en tant que tableau. Il se compose de nombres positifs supérieurs ou égaux à 0.

Remarquez ici que l'entier le plus élevé est de 20. Ainsi, 20 + 1 = 21, les nouveaux emplacements de tableau doivent être fournis. Le 1 EXTRI est pour la possibilité que l'un des entiers à tri est 0. N'oubliez pas que le programme de tri ne sait pas que les chiffres soient triés à l'avance. Donc, la possibilité d'avoir 0 devrait être faite.

Pour chaque index du nouveau tableau qui correspond à une valeur dans la liste donnée, le nombre d'occurrence de la valeur dans la liste donnée est attribué comme valeur pour cette nouvelle cellule de tableau. C'est-à-dire que le nouveau tableau se compose de compteurs. La liste précédente non triée est représentée comme suit:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	dix	11	12	13	14	15	16	17	18	19	20

Ce tableau représente un tableau qui est le nouveau tableau de compteurs. À ce stade, il y a deux tableaux: le tableau donné de la liste non triée et le tableau de compteurs appelés le tableau de comte.

Dans le tableau, la deuxième ligne a les index. La première ligne a le compte. Chaque nombre est le nombre d'occurrence de l'indice correspondant trouvé comme la valeur dans la liste non triée.

Pour les index 0 à 7 (inclus), le nombre est 0. En effet, aucun de ces index n'est une valeur dans la liste non triée. L'index 8 se produit une fois dans la liste, donc son nombre est 1. L'index 9 se produit zéro fois dans la liste, donc son nombre est 0. L'indice 10 se produit une fois dans la liste, donc son nombre est 1. L'index 12 se produit trois fois dans la liste, donc son nombre est 3. L'index 13 se produit zéro fois dans la liste, donc son nombre est 0. Cela se poursuit jusqu'à l'indice 20 avec un décompte de 1 tandis que l'index 18 a un décompte de 2.

La liste triée est la suivante:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Ceci peut être obtenu à partir du tableau de comte (nouveau) comme suit:

En passant de gauche à droite, si la valeur d'un index est de 0, cette valeur n'est pas dans la liste non triée (tableau) donnée. Si la valeur est 1, tapez l'index une fois. Si la valeur est 2, tapez l'index deux fois. Si la valeur est 3, tapez l'index trois fois. Si la valeur est 4, tapez l'index 4 fois, etc. Tout cela peut être fait sur le tableau non trié donné (liste).

Algorithme de tri à comptage

• Fournir un tableau dont la longueur est le nombre maximum dans la liste non triée, plus 1 (pour tenir compte d'un 0 possible dans la liste). L'indice de ce tableau est une valeur possible dans la liste non triée.
• Lisez le tableau de comptage de gauche à droite puis tapez l'index dont la valeur n'est pas 0 et le nombre de fois pour la valeur cellulaire de l'indice.

Opérations

L'algorithme a deux étapes. Pour la liste donnée précédente, la première étape a 10 opérations principales car le nombre d'éléments dans la liste non triée est de 10. La deuxième étape a 21 opérations principales car la valeur maximale dans la liste non triée est de 20 (le 1 supplémentaire étant pour une valeur 0 possible). Ainsi, le nombre des opérations principales est considéré comme suit:

O (10 + 20)

Où 10 est le nombre d'éléments dans la liste non triée et 20 est la valeur maximale dans la liste non triée. Le 1 à 20 ajouté est ignoré à ce stade, mais gardez à l'esprit qu'il doit être codé.

Complexité du temps pour compter le tri

La complexité du temps est le nombre approximatif des principales opérations pour un code. La complexité du temps indique la vitesse du code. La complexité du temps pour le rythme de comptage est donnée comme suit:

O (n + m)

Où n est le nombre d'éléments (longueur ou taille) du tableau non trié donné, et m est la valeur maximale dans le tableau non trié donné. Le 1 à M ajouté est ignoré à ce stade. Le Big-O avec ses parenthèses et son contenu est appelé la notation Big-O.

Notez que pour obtenir la valeur maximale dans le tableau, certaines opérations doivent se produire dans le code. Cependant, ces opérations sont ignorées lorsqu'ils citent la complexité temporelle.

Le tableau de comte doit avoir tous ses éléments initialement faits comme zéro. Toutes ces opérations sont également ignorées lors de la citation de complexité temporelle pour le tri de comptage.

Espace mémoire

Notez que dans le tableau de comptage précédent, tous les dénombrements de 0 sont redondants. Bien que leurs espaces soient redondants en mémoire, ils doivent être là. Le tri de comptage prend un espace mémoire inutile en général. Rien n'est normalement fait pour éviter les emplacements redondants. Si la valeur minimale dans le réseau non trié donné peut être connu, la partie débutant du tableau de comptage peut être omise pour réduire l'espace. Cependant, les zéros entrecoupés dans le tableau de comptage ne peuvent pas être omis.

Remarque: il y a aussi la complexité de l'espace, mais cela n'est pas abordé dans cet article.

Codage en c

Une fonction de rythme de comptage dans le langage informatique C est la suivante:

void comptagesort (int arr [], int n)
int max = 0;
pour (int i = 0; i max)
max = arr [i];


int count [max + 1];
pour (int i = 0; i< max+1; i++)
compter [i] = 0;

// n
pour (int i = 0; i< n; i++)
count [arr [i]] = count [arr [i]] + 1; // ajouter 1 pour chaque occurrence

// m
int k = 0; // Index pour le tableau donné
pour (int i = 0; iif (compter [i] != 0)
pour (int j = 0; jarr [k] = i; // remettre la valeur triée dans le tableau donné
k ++;

La boucle et l'entrée imbriquées sont les suivantes:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Il y a en fait 24 opérations majeures et non 20. L'opération 3 + 1 = 4 supplémentaire est ignorée lors de la citation de complexité temporelle pour le tri de comptage.

Une fonction principale C appropriée est la suivante:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
compter (arr, n);
pour (int i = 0; iprintf ("% d", arr [i]);
printf ("\ n");
retour 0;

La sortie est:

8 10 12 12 12 14 16 18 18 20

Conclusion

La complexité du temps pour le tri de comptage est:

O (n + m)

Où m est généralement supérieur à n, n est le nombre d'éléments (longueur) de la liste non triée donnée, et m est l'élément maximum de la liste non triée donnée.