Dans cet article, nous discuterons de l’algorithme de tri Radix. Le tri par base est l'algorithme de tri linéaire utilisé pour les entiers. Dans le tri Radix, un tri chiffre par chiffre est effectué, commençant du chiffre le moins significatif au chiffre le plus significatif.
Le processus de tri par base fonctionne de la même manière que le tri des noms des étudiants, selon l'ordre alphabétique. Dans ce cas, 26 bases sont formées grâce aux 26 alphabets anglais. Lors du premier passage, les noms des étudiants sont regroupés selon l'ordre croissant de la première lettre de leur nom. Après cela, lors du deuxième passage, leurs noms sont regroupés selon l'ordre croissant de la deuxième lettre de leur nom. Et le processus continue jusqu'à ce que nous trouvions la liste triée.
convertir une chaîne en char java
Voyons maintenant l'algorithme de tri Radix.
Algorithme
radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -> 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place
Fonctionnement de l'algorithme de tri Radix
Voyons maintenant le fonctionnement de l'algorithme de tri Radix.
Les étapes utilisées dans le tri du tri par base sont répertoriées comme suit :
- Tout d’abord, nous devons trouver le plus grand élément (supposons maximum ) à partir du tableau donné. Supposer 'X' être le nombre de chiffres dans maximum . Le 'X' est calculé car nous devons passer par les endroits significatifs de tous les éléments.
- Après cela, parcourez un par un chaque endroit important. Ici, nous devons utiliser n'importe quel algorithme de tri stable pour trier les chiffres de chaque lieu significatif.
Voyons maintenant le fonctionnement du tri par base en détail à l'aide d'un exemple. Pour le comprendre plus clairement, prenons un tableau non trié et essayons de le trier en utilisant le tri par base. Cela rendra l’explication plus claire et plus facile.
Dans le tableau donné, le plus grand élément est 736 qui ont 3 chiffres dedans. Ainsi, la boucle sera exécutée jusqu'à trois fois (c'est-à-dire jusqu'au lieu de centaines ). Cela signifie que trois passes sont nécessaires pour trier le tableau.
Maintenant, triez d'abord les éléments sur la base des chiffres de place unitaires (c'est-à-dire, x = 0 ). Ici, nous utilisons l'algorithme de tri par comptage pour trier les éléments.
Passe 1 :
Lors du premier passage, la liste est triée sur la base des chiffres à la place 0.
Après le premier passage, les éléments du tableau sont -
convertir la chaîne en int java
Passe 2 :
Dans cette passe, la liste est triée sur la base des prochains chiffres significatifs (c'est-à-dire les chiffres à 10èmelieu).
Après le deuxième passage, les éléments du tableau sont -
Passe 3 :
Dans cette passe, la liste est triée sur la base des prochains chiffres significatifs (c'est-à-dire les chiffres à 100èmelieu).
Après le troisième passage, les éléments du tableau sont -
Désormais, le tableau est trié par ordre croissant.
Complexité du tri Radix
Voyons maintenant la complexité temporelle du tri Radix dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale du tri Radix.
1. Complexité temporelle
| Cas | Complexité temporelle |
|---|---|
| Meilleur cas | Ω(n+k) |
| Cas moyen | θ(nk) |
| Pire cas | O (nk) |
Le tri Radix est un algorithme de tri non comparatif meilleur que les algorithmes de tri comparatifs. Il a une complexité temporelle linéaire meilleure que les algorithmes comparatifs de complexité O (n logn).
2. Complexité spatiale
| Complexité spatiale | O(n+k) |
| Écurie | OUI |
- La complexité spatiale du tri Radix est O(n + k).
Implémentation du tri Radix
Voyons maintenant les programmes de Radix triés dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le tri Radix en langage 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 countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix 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 countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarray(a,n); radixsort(a, n); cout<<'
after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { 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 countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); console.write('
after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { 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 countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are -
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('
after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>