Tri par base Java

Le tri Radix en Java est un algorithme de tri d'entiers qui utilise des clés entières et regroupe les clés avec des chiffres individuels partageant la même position significative et la même valeur de position. Ensuite, les éléments sont triés par ordre croissant/décroissant. L'idée principale du tri Radix est d'effectuer un tri chiffre par chiffre en commençant par le chiffre le moins significatif jusqu'au chiffre le plus significatif. Il utilise le tri par comptage comme sous-programme pour trier un tableau de nombres. Le tri Radix intègre le tri par comptage afin de pouvoir trier des chiffres volumineux et à plusieurs chiffres sans avoir à diminuer son efficacité en augmentant la gamme de clés que l'algorithme trierait. Approfondissons le tri Radix et voyons comment le tri Radix fonctionne en Java avec quelques exemples.

Commencez votre cours de développement de logiciels libres

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

Syntaxe

Le tri Radix comporte des étapes d'algorithme ou un organigramme expliquant comment le tri est effectué. Regardons donc l'algorithme de tri par base.

Algorithme de tri par base

Étape 1 : Tout d'abord, nous devons trouver le plus grand élément du tableau, c'est-à-dire l'élément max. Et considérons X comme le nombre de chiffres dans l'élément maximum.

Nous devons calculer X car nous devons passer par la valeur de position d'un élément maximum.

Étape 2 : Maintenant, nous devons passer en revue chaque valeur de position de l'élément maximum.

Étape 3 : Nous devons utiliser n'importe quel algorithme de tri stable pour trier les chiffres à chaque valeur de position significative.

Étape 4 : Les éléments sont désormais triés en fonction des chiffres à la valeur de position unitaire {X=0}

Étape 5 : Ensuite, triez les éléments en fonction des chiffres à la place des dizaines {X=10}

Étape 6 : Ensuite, triez les éléments en fonction des chiffres à la place des centaines {X=100}

Étape 7 : L'étape ci-dessus se répète s'il y a d'autres valeurs de position pour les éléments dans le tableau, c'est-à-dire en fonction de la valeur X.

Comment le tri Radix est-il effectué en Java ?

Vérifions comment le tri Radix est implémenté avec quelques exemples.

Exemple n°1

Code :

import java.util.*;
public class radixSorting {
static int get_maxVal(int radixArr[], int arrLen) {
int maxVal = radixArr[0];
for (int i = 1; i < arrLen; i++)
if (radixArr[i] > maxVal)
maxVal = radixArr[i];
return maxVal;
}
static void countSorting(int radixArr[], int arrLen, int exp) {
int resultArray[] = new int[arrLen];
int i;
int countVal[] = new int[10];
Arrays.fill(countVal,0);
for (i = 0; i < arrLen; i++)
countVal[ (radixArr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
countVal[i] += countVal[i - 1];
for (i = arrLen - 1; i >= 0; i--) {
resultArray[countVal[ (radixArr[i]/exp)%10 ] - 1] = radixArr[i];
countVal[ (radixArr[i]/exp)%10 ]--;
}
for (i = 0; i < arrLen; i++)
radixArr[i] = resultArray[i];
}
static void radix_array_sort(int radixArr[], int arrLen) {
int m = get_maxVal(radixArr, arrLen);
for(int exp = 1; m/exp > 0; exp *= 10)
countSorting(radixArr, arrLen, exp);
}
public static void main (String[] args) {
int radixArr[] = {32,456,71,10,9,892,55,90,23,667};
int arrLen = radixArr.length;
System.out.println("Array after radix sort is ");
radix_array_sort(radixArr, arrLen);
for (int i=0; i<arrLen; i++)
System.out.print(radixArr[i]+" ");
}
}

Sortie :

Donc ici, nous pouvons voir que le tableau d'entrée a été trié en utilisant le tri Radix avec le tri Counting.

Exemple n°2

Code :

import java.util.Arrays;
public class RadixSorting {
public static void sorting(int[] inputArray) {
RadixSorting.sorting(inputArray, 10);
}
public static void sorting(int[] inputArray, int radix) {
if (inputArray.length == 0) {
return;
}
int minVal = inputArray[0];
int maxVal = inputArray[0];
for (int i = 1; i < inputArray.length; i++) {
if (inputArray[i] < minVal) {
minVal = inputArray[i];
} else if (inputArray[i] > maxVal) {
maxVal = inputArray[i];
}
}
int exponentVal = 1;
while ((maxVal - minVal) / exponentVal >= 1) {
RadixSorting.countingSort_by_digit(inputArray, radix, exponentVal, minVal);
exponentVal *= radix;
}
}
private static void countingSort_by_digit(
int[] inputArray, int radix, int exponentVal, int minVal) {
int bucket_index;
int[] bucket = new int[radix];
int[] output = new int[inputArray.length];
for (int i = 0; i < radix; i++) {
bucket[i] = 0;
}
for (int i = 0; i < inputArray.length; i++) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
bucket[bucket_index]++;
}
for (int i = 1; i < radix; i++) {
bucket[i] += bucket[i - 1];
}
for (int i = inputArray.length - 1; i >= 0; i--) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
output[--bucket[bucket_index]] = inputArray[i];
}
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = output[i];
}
}
public static void main(String args[])
{
RadixSorting rs = new RadixSorting();
int radix_input[] = {72, 15, 30, 21, 13, 944, 417};
System.out.println("Original Input Array:");
System.out.println(Arrays.toString(radix_input));
rs.sorting(radix_input);
System.out.println("Sorted Array using Radix Sort:");
System.out.println(Arrays.toString(radix_input));
}
}

Sortie :

Donc ici, nous utilisons une logique différente pour trier le tableau d'entrée à l'aide de Radix Sort.

Maintenant, laissez-moi vous expliquer ou vous montrer comment le tri Radix est effectué avec un exemple en direct,

Nous prendrons le tableau d'entrée comme [72, 15, 30, 21, 13, 944, 417]

Étape 1 : Obtenez la valeur maximale du tableau, c'est-à-dire 944. Donc, maintenant la valeur X serait 3, c'est-à-dire X = non. de chiffres dans l'élément Maximum, ce qui signifie en fait que la disposition du tableau se ferait en trois fois

Étape 2 : Nous allons donc maintenant essayer d'organiser les nombres sur la base du chiffre le moins significatif.

Considérant la valeur de position de l'unité de tous les éléments, le tableau sera réorganisé comme ci-dessous,

[30, 21, 72, 13, 944, 15, 417]

Considérant la valeur des dizaines de tous les éléments, le tableau sera réorganisé comme ci-dessous,

[13, 15, 417, 21, 30, 944, 72]

Considérant la valeur de position en centaines de tous les éléments, le cas échéant, le tableau sera réorganisé comme ci-dessous,

[13, 15, 21, 30, 72, 417, 944]

Étape 3 : Ça y est, les tableaux ont été triés.

Conclusion

Avec cela, nous conclurons l'article « Tri Radix en Java ». Nous avons vu ce qu'est le tri Radix et comment il est implémenté à l'aide du tri par comptage. C'est l'une des formes de tri les plus simples et elle est également plus rapide si les clés sont courtes, c'est-à-dire que la gamme d'éléments est moindre. Au cours des dernières années, les techniques de tri ont été largement utilisées au quotidien par les algorithmes. Cependant, il existe également certains inconvénients ; Le tri par base dépend beaucoup de l'entrée, c'est-à-dire des lettres ou des chiffres, et est donc moins flexible que les autres tris.

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!