Tri par comptage en Java

Counting Sort est un algorithme qui joue un rôle central dans tout langage de programmation, tout comme Java. L'objectif principal de l'algorithme de tri par comptage est de trier la collection d'objets en fonction de clés présentes sous forme de petits entiers pour trier les algorithmes. Il fonctionne et effectue principalement le décompte sur la paire clé-valeur, présente le positionnement des éléments selon la séquence de sortie.  Le temps d'exécution de ce tri est linéaire en termes d'éléments, puis la différence entre les valeurs clés se situe entre maximum et minimum.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Syntaxe

Il n'y a pas de syntaxe spécifique pour effectuer le tri par comptage en Java, mais il existe un flux logique qui est appliqué sous la forme d'un algorithme étape par étape pour effectuer le tri par comptage selon l'entrée et est représenté comme suit :

Class name {
Method name following sorting ()
{
# Find the length of array defined;
#the output character array will have sorted array
#Create a count arr to store count of each element, characters and initialize it 0
#Store count of each character element in the array
#Build output character and write the logic to make it operated in reverse order
#that builds output can now be copied from the previous array to the current
#Make use of the driver code to move and proceed.
}

Comment fonctionne le tri par comptage en Java ?

• Comme mentionné, l'algorithme Counting Sort joue un rôle important dans la programmation ; il fonctionne sur le tri des objets présents dans un format collecté et est utilisé pour compter le nombre d'éléments présents qui ont une paire clé-valeur distincte et est à nouveau utilisé avec les comptes arithmétiques déterminant la position de chaque élément présent avec chaque clé-valeur ayant la différence entre les valeurs minimales et maximales.
• Le temps d'exécution ou la complexité temporelle, s'il est coché, est de nature linéaire avec tous les éléments du tableau et la différence entre les valeurs de clé minimale et maximale, donc ces éléments et cette technique de tri conviennent en cas d'utilisation directe où les variations de clés ne sont pas significativement supérieurs aux éléments présents avec la clé requise.
• Bien qu'il existe un autre algorithme qui peut prendre en charge la plupart de la gestion des clés, il n'est pas si efficace car le tri par comptage selon les exigences et le hachage peuvent donc être remplacés par le tri Radix pour gérer la situation d'une grande quantité de clé par rapport au précédent. .
• Étant donné que le tri par comptage utilise une paire clé et valeur dans le cadre de la valeur d'index dans un tableau, il n'est donc pas considéré comme un tri par comparaison. De plus, la limite inférieure du tri par comparaison n'y est pas autorisée.
• Le tri par compartiment comprend également le tri sous-comptage uniquement avec le même ensemble de tâches et une analyse de temps similaire, mais par rapport au tri par comptage, à ce moment-là, le tri par compartiment nécessite des tableaux dynamiques, des listes chaînées ou une grande quantité de mémoire à conserver. les éléments présents dans le compartiment, puis le tri par comptage, ne stocke que les valeurs qui sont individuelles et uniques selon le compartiment.
• Il existe certaines séquences hypothétiques d'entrée et de sortie qui reposent sur le fait que l'entrée du tri par comptage consiste en une collection de n éléments où chaque élément a des valeurs clés entières non négatives pour la valeur maximale ayant une valeur comme k. certaines descriptions du tri par comptage sont l'entrée pour trier simplement une séquence d'entiers au format linéaire.
• La sortie d'un tableau ne se compose généralement pas d'éléments majeurs avec un certain ordre de clé, mais son utilisation doit être vérifiée par rapport aux exigences.
• La complexité temporelle par rapport au comptage Tri s'avère être O (n+l), où n est le nombre d'éléments et l est la plage de prise en compte de l'entrée.
• De plus, l'espace auxiliaire s'avère être uniquement O(n+l).

Exemple de tri par comptage en java

Ce programme démontre le tri par comptage en considérant une partie de la séquence d'entrée et de sortie définie dans le cadre du tri en Java.

Code :

public class Counting_Sort_1{
void sort_0(char arr_0[])
{
int n_8 = arr_0.length;
char output_val[] = new char[n_8];
int count_0[] = new int[528];
for (int l_0 = 0; l_0 < 528; ++l_0)
count_0[l_0] = 0;
for (int y_1 = 0; y_1 < n_8; ++y_1)
++count_0[arr_0[y_1]];
for (int l_0 = 1; l_0 <= 526; ++l_0)
count_0[l_0] += count_0[l_0 - 1];
for (int l_0 = n_8 - 1; l_0 >= 0; l_0--) {
output_val[count_0[arr_0[l_0]] - 1] = arr_0[l_0];
--count_0[arr_0[l_0]];
}
for (int l_0 = 0; l_0 < n_8; ++l_0)
arr_0[l_0] = output_val[l_0];
}
public static void main(String []args){
Counting_Sort_1 ob = new Counting_Sort_1();
char arr_0[] = { 's', 'a', 'r', 'c', 's', 'f', 'o',
'i', 'n', 'c', 'a', 'r', 'm' };
ob.sort_0(arr_0);
System.out.print("Sorted_character_array_in_Counting_Sort ");
for (int l = 0; l < arr_0.length; ++l)
System.out.print(arr_0[l]);
}
}

Sortie :

Explication

Dans l'exemple ci-dessus, nous avons implémenté le tri par comptage en Java où les étapes suivantes ont été suivies pour une exécution correcte :

• Une classe avec Selection_Sort_0 est créée ensuite suite à l'ensemble des entrées dans la classe.
• Une fois la classe créée, une méthode a été créée pour stocker le tableau de caractères qui aura un tableau trié.
• Création d'un tableau de comptage avec le sens de stocker la valeur en tant qu'entité indépendante sous la forme d'une paire clé et valeur. De plus, elle est stockée sous forme de caractère en tant que nombre.
• Une modification du nombre est requise pour compter la valeur réelle et la position du caractère actuel dans le tableau de sortie.
• Construire le tableau de sortie avec l'ensemble de caractères pour le rendre stable et utilisable dans l'ordre inverse.
• Copier le tableau trié dans le tableau actuel pour trier le tableau d'une manière ou d'une autre.
• Le code du pilote est exécuté pour piloter l'ensemble de la base de code afin d'obtenir la sortie de la source d'entrée.

Conclusion

Le tri par comptage est un type d'algorithme de tri qui est appliqué sur un tableau composé d'une plage d'éléments à trier. Le tri sera basé sur les paires clé et valeur qui seront présentes dans le tableau ou sur la différence entre la valeur minimale et la valeur maximale. Counting Sorting a fourni beaucoup d'aide aux développeurs lorsqu'il est nécessaire d'implémenter l'utilisation de nombres entiers en masse.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!