Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η ταξινόμηση ακτίνων. Επίσης, θα βρείτε λειτουργικά παραδείγματα ταξινόμησης ακτίνων σε C, C ++, Java και Python.
Το Radix sort είναι μια τεχνική ταξινόμησης που ταξινομεί τα στοιχεία ομαδοποιώντας πρώτα τα μεμονωμένα ψηφία της ίδιας τιμής θέσης . Στη συνέχεια, ταξινομήστε τα στοιχεία σύμφωνα με την αυξανόμενη / φθίνουσα σειρά τους.
Ας υποθέσουμε ότι έχουμε μια σειρά από 8 στοιχεία. Πρώτον, θα ταξινομήσουμε στοιχεία με βάση την τιμή του μέρους της μονάδας. Στη συνέχεια, θα ταξινομήσουμε στοιχεία με βάση την τιμή της δέκατης θέσης. Αυτή η διαδικασία συνεχίζεται μέχρι την τελευταία σημαντική θέση.
Αφήστε τον αρχικό πίνακα να είναι (121, 432, 564, 23, 1, 45, 788). Ταξινομήθηκε σύμφωνα με την ταξινόμηση ακτίνων όπως φαίνεται στο παρακάτω σχήμα.
Εργασία του Radix Sort
Διαβάστε το είδος καταμέτρησης προτού διαβάσετε αυτό το άρθρο επειδή το είδος καταμέτρησης χρησιμοποιείται ως ενδιάμεσο είδος σε είδος ακτίνας.
Πώς λειτουργεί το Radix Sort;
- Βρείτε το μεγαλύτερο στοιχείο στον πίνακα, δηλ. Μέγ. Ας
Xείναι ο αριθμός των ψηφίων σεmax.Xυπολογίζεται επειδή πρέπει να περάσουμε από όλα τα σημαντικά σημεία όλων των στοιχείων.
Σε αυτόν τον πίνακα(121, 432, 564, 23, 1, 45, 788), έχουμε τον μεγαλύτερο αριθμό 788. Έχει 3 ψηφία. Επομένως, ο βρόχος πρέπει να φτάσει έως και εκατοντάδες θέσεις (3 φορές). - Τώρα, περάστε από κάθε σημαντικό μέρος ένα προς ένα.
Χρησιμοποιήστε οποιαδήποτε σταθερή τεχνική ταξινόμησης για να ταξινομήσετε τα ψηφία σε κάθε σημαντικό μέρος. Έχουμε χρησιμοποιήσει είδος καταμέτρησης για αυτό.
Ταξινόμηση των στοιχείων με βάση τα ψηφία θέσης μονάδας (X=0).
Χρήση καταμέτρησης ταξινόμησης για ταξινόμηση στοιχείων με βάση τη θέση μονάδας - Τώρα, ταξινομήστε τα στοιχεία με βάση τα ψηφία σε δεκάδες θέσεις.
Ταξινόμηση στοιχείων με βάση δεκάδες μέρος - Τέλος, ταξινομήστε τα στοιχεία με βάση τα ψηφία σε εκατοντάδες θέσεις.
Ταξινόμηση στοιχείων με βάση εκατοντάδες μέρος
Αλγόριθμος ταξινόμησης Radix
radixSort (array) d <- ο μέγιστος αριθμός ψηφίων στο μεγαλύτερο στοιχείο δημιουργεί d κάδους μεγέθους 0-9 για i <- 0 για d ταξινόμηση των στοιχείων σύμφωνα με ith ψηφία θέσης χρησιμοποιώντας καταμέτρηση Ταξινόμηση μέτρησης Ταξινόμηση (πίνακας, d) max <- εύρεση το μεγαλύτερο στοιχείο μεταξύ των στοιχείων θέσης dth αρχικοποιεί τον πίνακα μετρήσεων με όλα τα μηδενικά για το j <- 0 στο μέγεθος βρείτε το συνολικό πλήθος κάθε μοναδικού ψηφίου στη θέση των στοιχείων και αποθηκεύστε τον αριθμό στο ευρετήριο jth στον πίνακα μετρήσεων για i <- 1 έως το μέγιστο εύρημα το αθροιστικό άθροισμα και αποθηκεύστε το στο ίδιο τον πίνακα συστοιχιών για το j <- μέγεθος έως 1 επαναφέρετε τα στοιχεία στη συστοιχία μειώστε τον αριθμό κάθε στοιχείου που αποκαθίσταται κατά 1
Παραδείγματα Python, Java και 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); )
Περίπλοκο
Δεδομένου ότι η ταξινόμηση ακτίνων είναι ένας μη συγκριτικός αλγόριθμος, έχει πλεονεκτήματα έναντι των αλγορίθμων συγκριτικής ταξινόμησης.
Για το είδος ακτίνας που χρησιμοποιεί την ταξινόμηση καταμέτρησης ως ενδιάμεσο σταθερό είδος, η πολυπλοκότητα του χρόνου είναι O(d(n+k)).
Εδώ, dείναι ο κύκλος αριθμών και O(n+k)είναι η χρονική πολυπλοκότητα του είδους καταμέτρησης.
Έτσι, η ταξινόμηση ακτίνων έχει γραμμική πολυπλοκότητα χρόνου που είναι καλύτερη από O(nlog n)συγκριτικούς αλγόριθμους ταξινόμησης.
Εάν παίρνουμε πολύ μεγάλους αριθμούς ψηφίων ή τον αριθμό άλλων βάσεων όπως αριθμούς 32-bit και 64-bit τότε μπορεί να αποδώσει σε γραμμικό χρόνο, ωστόσο το ενδιάμεσο είδος παίρνει μεγάλο χώρο.
Αυτό καθιστά το χώρο ταξινόμησης ακτίνων αναποτελεσματικό. Αυτός είναι ο λόγος για τον οποίο αυτό το είδος δεν χρησιμοποιείται σε βιβλιοθήκες λογισμικού.
Εφαρμογές ταξινόμησης Radix
Το είδος Radix υλοποιείται το
- Αλγόριθμος DC3 (Kärkkäinen-Sanders-Burkhardt) κατά τη δημιουργία ενός πίνακα επιθημάτων.
- μέρη όπου υπάρχουν αριθμοί σε μεγάλες περιοχές.
