Αλγόριθμος ταξινόμησης ριζών στη δομή δεδομένων
Τι είναι ο αλγόριθμος ταξινόμησης Radix;
Το Radix Sort είναι ένας μη συγκριτικός αλγόριθμος ταξινόμησης. Λειτουργεί ομαδοποιώντας τα μεμονωμένα ψηφία των προς ταξινόμηση στοιχείων. Στη συνέχεια χρησιμοποιείται μια σταθερή τεχνική ταξινόμησης για την οργάνωση των στοιχείων με βάση την ρίζα τους. Είναι ένας αλγόριθμος γραμμικής ταξινόμησης.
Η διαδικασία ταξινόμησης περιλαμβάνει τις ακόλουθες ιδιότητες:
- Εύρεση του μέγιστου στοιχείου και απόκτηση του αριθμού των ψηφίων αυτού του στοιχείου. Μας δίνει τον αριθμό των επαναλήψεων που θα ακολουθήσει η διαδικασία ταξινόμησης.
- Ομαδοποιήστε τα μεμονωμένα ψηφία των στοιχείων στην ίδια σημαντική θέση σε κάθε επανάληψη.
- Η διαδικασία ομαδοποίησης θα ξεκινά από το λιγότερο σημαντικό ψηφίο και θα τελειώνει στο πιο σημαντικό ψηφίο.
- Ταξινόμηση των στοιχείων με βάση ψηφία σε αυτή τη σημαντική θέση.
- Διατήρηση της σχετικής σειράς στοιχείων που έχουν την ίδια τιμή κλειδιού. Αυτή η ιδιότητα της ταξινόμησης ρίζας την καθιστά σταθερή ταξινόμηση.
Η τελική επανάληψη θα μας δώσει μια πλήρως ταξινομημένη λίστα.
Εργασία Αλγόριθμου Ταξινόμησης Radix

Ας προσπαθήσουμε να ταξινομήσουμε τη λίστα των ακεραίων στο παραπάνω σχήμα σε αύξουσα σειρά χρησιμοποιώντας τον αλγόριθμο Ταξινόμησης Radix.
Ακολουθούν τα βήματα για να εκτελέσετε τη διαδικασία ταξινόμησης ριζών:
Βήμα 1) Προσδιορίστε το στοιχείο με τη μέγιστη τιμή στη λίστα. Σε αυτήν την περίπτωση, είναι 835.
Βήμα 2) Υπολογίστε τον αριθμό των ψηφίων του μέγιστου στοιχείου. Το 835 έχει 3 ψηφία ακριβώς.
Βήμα 3) Προσδιορίστε τον αριθμό των επαναλήψεων με βάση το βήμα 2. Το 835 έχει 3 ψηφία, που σημαίνει ότι ο αριθμός των επαναλήψεων θα είναι 3.
Βήμα 4) Προσδιορίστε τη βάση των στοιχείων. Δεδομένου ότι αυτό είναι ένα δεκαδικό σύστημα, η βάση θα είναι 10.
Βήμα 5) Ξεκινήστε την πρώτη επανάληψη.
α) Πρώτη επανάληψη

Στην πρώτη επανάληψη, εξετάζουμε τη μοναδιαία θέση αξίας κάθε στοιχείου.
Βήμα 1) Τροποποιήστε τον ακέραιο κατά 10 για να λάβετε τη θέση μονάδας των στοιχείων. Για παράδειγμα, το 623 mod 10 μας δίνει την τιμή 3 και το 248 mod 10 μας δίνει 8.
Βήμα 2) Χρησιμοποιήστε ταξινόμηση μέτρησης ή οποιαδήποτε άλλη σταθερή ταξινόμηση για να οργανώσετε τους ακέραιους αριθμούς σύμφωνα με το λιγότερο σημαντικό ψηφίο τους. Όπως φαίνεται Από το σχήμα, 248 θα πέσουν στον 8ο κάδο. 623 θα πέσει στον 3ο κουβά κ.ο.κ.
Μετά την πρώτη επανάληψη, η λίστα μοιάζει τώρα με αυτό.

Όπως μπορείτε να δείτε από το παραπάνω σχήμα, η λίστα δεν έχει ταξινομηθεί ακόμα και απαιτεί περισσότερη επανάληψη για την πλήρη ταξινόμηση.
β) Δεύτερη επανάληψη

Σε αυτή την επανάληψη, θα εξετάσουμε το ψηφίο στο 10th θέση για τη διαδικασία διαλογής.
Βήμα 1) Διαιρέστε τους ακέραιους με το 10. Το 248 διαιρούμενο με το 10 μας δίνει 24.
Βήμα 2) Διαμορφώστε την έξοδο του βήματος 1 κατά 10. Το 24 mod 10 μας δίνει 4.
Βήμα 3) Ακολουθήστε το βήμα 2 από την προηγούμενη επανάληψη.
Μετά τη δεύτερη επανάληψη, η λίστα μοιάζει τώρα με αυτό

Μπορείτε να δείτε από το παραπάνω σχήμα ότι η λίστα εξακολουθεί να μην έχει ταξινομηθεί πλήρως, καθώς δεν είναι ακόμη σε αύξουσα σειρά.
γ) Τρίτη επανάληψη

Για την τελική επανάληψη, θέλουμε να πάρουμε το πιο σημαντικό ψηφίο. Σε αυτή την περίπτωση, είναι το 100th θέση για καθέναν από τους ακέραιους στη λίστα.
Βήμα 1) Διαιρούμε τους ακέραιους με το 100… Το 415 διαιρούμενο με το 100 μας δίνει το 4.
Βήμα 2) Mod το αποτέλεσμα από το βήμα 1 με 10. 4 mod 10 μας δίνει ξανά 4.
Βήμα 3) Ακολουθήστε το βήμα 3 από την προηγούμενη επανάληψη.

Όπως μπορούμε να δούμε, η λίστα ταξινομείται τώρα με αύξουσα σειρά. Η τελική επανάληψη έχει ολοκληρωθεί και η διαδικασία ταξινόμησης έχει πλέον ολοκληρωθεί.
Ψευδοκώδικας αλγόριθμου ταξινόμησης ριζών
Εδώ είναι ο ψευδοκώδικας για τον αλγόριθμο ταξινόμησης Radix
radixSortAlgo(arr as an array) Find the largest element in arr maximum=the element in arr that is the largest Find the number of digits in maximum k=the number of digits in maximum Create buckets of size 0-9 k times for j -> 0 to k Acquire the jth place of each element in arr. Here j=0 represents the least significant digit. Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace arr = sorted elements
C++ Πρόγραμμα για την εφαρμογή Radix Sort
#include <iostream> using namespace std; // Function to get the largest element in an array int getMaximum(int arr[], int n) { int maximum = arr[0]; for (int i = 1; i < n; i++) { if (maximum < arr[i]) maximum = arr[i]; } return maximum; } // We are using counting sort to sort the elements digit by digit void countingSortAlgo(int arr[], int size, int position) { const int limit = 10; int result[size]; int count[limit] = {0}; // Calculating the count of each integers for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++; // Calculating the cumulative count for (int j = 1; j < limit; j++) { count[j] += count[j - 1]; } // Sort the integers for (int j = size - 1; j >= 0; j--) { result[count[(arr[j] / position) % 10] - 1] = arr[j]; count[(arr[j] / position) % 10]--; } for (int i = 0; i < size; i++) arr[i] = result[i]; } // The radixSort algorithm void radixSortAlgo(int arr[], int size) { // Get the largest element in the array int maximum = getMaximum(arr, size); for (int position = 1; maximum / position > 0; position *= 10) countingSortAlgo(arr, size, position); } // Printing final result void printResult(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int arr[] = {162, 623, 835, 415, 248}; int size = sizeof(arr) / sizeof(arr[0]); radixSortAlgo(arr, size); printResult(arr, size); }
Παραγωγή:
162 248 415 623 835
Python Πρόγραμμα για τον αλγόριθμο ταξινόμησης ριζών
#Radix Sort using python def countingSortAlgo(arr, position): n = len(arr) result = [0] * n count = [0] * 10 # Calculating the count of elements in the array arr for j in range(0, n): element = arr[j] // position count[element % 10] += 1 # Calculating the cumulative count for j in range(1, 10): count[j] += count[j - 1] # Sorting the elements i = n - 1 while i >= 0: element = arr[i] // position result[count[element % 10] - 1] = arr[i] count[element % 10] -= 1 i -= 1 for j in range(0, n): arr[j] = result[j] def radixSortAlgo(arr): # Acquiring the largest element in the array maximum = max(arr) # Using counting sort to sort digit by digit position = 1 while maximum // position > 0: countingSortAlgo(arr, position) position *= 10 input = [162, 623, 835, 415, 248] radixSortAlgo(input) print(input)
Παραγωγή:
[162,248,415,623,835]
Ανάλυση πολυπλοκότητας Radix Sort
Υπάρχουν δύο τύποι πολυπλοκότητας που πρέπει να ληφθούν υπόψη, η πολυπλοκότητα χώρου και η πολυπλοκότητα χρόνου.
- Πολυπλοκότητα χώρου: O(n+b) όπου n είναι το μέγεθος του πίνακα και b είναι η βάση που εξετάζεται.
- Χρονική πολυπλοκότητα: O(d*(n+b)) όπου d είναι ο αριθμός των ψηφίων του μεγαλύτερου στοιχείου του πίνακα.
Διαστημική πολυπλοκότητα του Radix Sort
Δύο χαρακτηριστικά στα οποία πρέπει να εστιάσετε για την πολυπλοκότητα του χώρου
- Αριθμός στοιχείων στον πίνακα, n.
- Η βάση για την αναπαράσταση των στοιχείων, b.
Μερικές φορές αυτή η βάση μπορεί να είναι μεγαλύτερη από το μέγεθος του πίνακα.
Η συνολική πολυπλοκότητα είναι επομένως O(n+b).
Οι ακόλουθες ιδιότητες των στοιχείων στη λίστα μπορούν να καταστήσουν τον χώρο ταξινόμησης βάσης αναποτελεσματικό:
- Στοιχεία με μεγάλο αριθμό ψηφίων.
- Η βάση των στοιχείων είναι μεγάλη, όπως αριθμοί 64 bit.
Χρονική πολυπλοκότητα ταξινόμησης ριζών
Μπορείτε να χρησιμοποιήσετε την ταξινόμηση μέτρησης ως υπορουτίνα, καθώς κάθε επανάληψη διαρκείe O(n+b) χρόνος. Εάν υπάρχουν d επαναλήψεις, γίνεται ο συνολικός χρόνος λειτουργίας O(d*(n+b)). Εδώ, το "O" σημαίνει τη συνάρτηση πολυπλοκότητας.
Γραμμικότητα Ταξινόμησης Radix
Η ταξινόμηση ριζών είναι γραμμική όταν
- d είναι σταθερό, όπου d είναι ο αριθμός των ψηφίων του μεγαλύτερου στοιχείου.
- b δεν είναι μεγαλύτερο σε μεγάλο βαθμό σε σύγκριση με n.
Συγκρίσεις Radix Sort με άλλους συγκριτικούς αλγόριθμους
Όπως είδαμε, η πολυπλοκότητα της ταξινόμησης Radix βασίζεται στο μέγεθος μιας λέξης ή ενός αριθμού. Θα έχει την ίδια πολυπλοκότητα για τις μέσες και καλύτερες περιπτώσεις. Και αυτό είναι O(d*(n+b)). Επίσης, διαφέρει ανάλογα με την τεχνική ταξινόμησης που χρησιμοποιείτε στη μέση. Για παράδειγμα, μπορείτε να χρησιμοποιήσετε ταξινόμηση μέτρησης ή γρήγορη ταξινόμηση για τον ενδιάμεσο αλγόριθμο ταξινόμησης εντός της ταξινόμησης Radix.
Εφαρμογές Αλγόριθμου Ταξινόμησης Radix
Σημαντικές εφαρμογές του Radix Sort είναι:
- Το Radix Sort μπορεί να χρησιμοποιηθεί ως αλγόριθμος εύρεσης τοποθεσίας όπου χρησιμοποιούνται μεγάλα εύρη τιμών.
- Χρησιμοποιείται για την κατασκευή ενός πίνακα επιθημάτων στον αλγόριθμο DC3.
- Χρησιμοποιείται σε ένα μηχάνημα διαδοχικής, τυχαίας πρόσβασης που υπάρχει σε έναν τυπικό υπολογιστή όπου πληκτρολογούνται οι εγγραφές.