Dans ce didacticiel, vous apprendrez comment fonctionne le tri radix. Vous trouverez également des exemples fonctionnels de tri radix en C, C ++, Java et Python.
Le tri Radix est une technique de tri qui trie les éléments en regroupant d'abord les chiffres individuels de la même valeur de position . Ensuite, triez les éléments selon leur ordre croissant / décroissant.
Supposons que nous ayons un tableau de 8 éléments. Tout d'abord, nous allons trier les éléments en fonction de la valeur de la place unitaire. Ensuite, nous trierons les éléments en fonction de la valeur de la dixième place. Ce processus se poursuit jusqu'à la dernière place significative.
Que le tableau initial soit (121, 432, 564, 23, 1, 45, 788). Il est trié selon le tri de base comme indiqué dans la figure ci-dessous.
Fonctionnement de Radix Sort
Veuillez passer par le tri par comptage avant de lire cet article car le tri par comptage est utilisé comme tri intermédiaire dans le tri par base.
Comment fonctionne le tri Radix?
- Trouvez le plus grand élément du tableau, c'est-à-dire max. Soit
Xle nombre de chiffres dansmax.Xest calculé parce que nous devons passer par tous les endroits significatifs de tous les éléments.
Dans ce tableau(121, 432, 564, 23, 1, 45, 788), nous avons le plus grand nombre 788. Il comporte 3 chiffres. Par conséquent, la boucle doit aller jusqu'à des centaines de places (3 fois). - Maintenant, parcourez chaque endroit significatif un par un.
Utilisez n'importe quelle technique de tri stable pour trier les chiffres à chaque endroit significatif. Nous avons utilisé le tri de comptage pour cela.
Triez les éléments en fonction des chiffres de lieu de l'unité (X=0).
Utilisation du tri par comptage pour trier les éléments en fonction de l'emplacement de l'unité - Maintenant, triez les éléments en fonction des chiffres à la dizaine.
Trier les éléments en fonction de la place des dizaines - Enfin, triez les éléments en fonction des chiffres à la place des centaines.
Trier les éléments en fonction de centaines de place
Algorithme de tri Radix
radixSort (array) d <- nombre maximum de chiffres dans le plus grand élément créer d buckets de taille 0-9 pour i <- 0 à d trier les éléments selon le ième chiffre à l'aide de countingSort countingSort (array, d) max <- find le plus grand élément parmi les éléments dth place initialise le tableau de comptage avec tous les zéros pour j <- 0 à la taille trouver le nombre total de chaque chiffre unique à la dth place des éléments et stocker le comptage au jième index dans le tableau de comptage pour i <- 1 à max find la somme cumulée et la stocker dans le tableau count lui-même pour j <- taille jusqu'à 1 restaurer les éléments dans le tableau diminuer le nombre de chaque élément restauré de 1
Exemples Python, Java et C / C ++
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Complexité
Étant donné que le tri radix est un algorithme non comparatif, il présente des avantages par rapport aux algorithmes de tri comparatif.
Pour le tri de base qui utilise le tri par comptage comme tri stable intermédiaire, la complexité temporelle est O(d(n+k)).
Voici dle cycle des nombres et O(n+k)la complexité temporelle du tri de comptage.
Ainsi, le tri par base a une complexité temporelle linéaire qui est meilleure que celle O(nlog n)des algorithmes de tri comparatif.
Si nous prenons de très grands nombres de chiffres ou le nombre d'autres bases comme des nombres de 32 bits et de 64 bits, alors cela peut fonctionner en temps linéaire, mais le tri intermédiaire prend un grand espace.
Cela rend l'espace de tri de base inefficace. C'est la raison pour laquelle ce tri n'est pas utilisé dans les bibliothèques de logiciels.
Applications de tri Radix
Le tri Radix est implémenté dans
- Algorithme DC3 (Kärkkäinen-Sanders-Burkhardt) tout en créant un tableau de suffixes.
- endroits où il y a des nombres dans de grandes gammes.
