Αλγόριθμος ταξινόμησης ριζών στη δομή δεδομένων

Τι είναι ο αλγόριθμος ταξινόμησης Radix;

Το Radix Sort είναι ένας μη συγκριτικός αλγόριθμος ταξινόμησης. Λειτουργεί κατά ομάδα.ping τα μεμονωμένα ψηφία των στοιχείων που πρόκειται να ταξινομηθούν. Στη συνέχεια, χρησιμοποιείται μια τεχνική σταθερής ταξινόμησης για την οργάνωση των στοιχείων με βάση την ακτίνα τους. Πρόκειται για έναν γραμμικό αλγόριθμο ταξινόμησης.

Η διαδικασία ταξινόμησης περιλαμβάνει τις ακόλουθες ιδιότητες:

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

Η τελική επανάληψη επιστρέφει μια πλήρως ταξινομημένη λίστα.

Εργασία Αλγόριθμου Ταξινόμησης Radix

Λίστα ακεραίων προς ταξινόμηση

Ας ταξινομήσουμε τη λίστα των ακεραίων στο παραπάνω σχήμα σε αύξουσα σειρά χρησιμοποιώντας την Radix Sort.

Ακολουθούν τα βήματα για την εκτέλεση της διαδικασίας Radix Sort:

Βήμα 1) Προσδιορίστε το μέγιστο στοιχείο στη λίστα. Εδώ είναι 835.

Βήμα 2) Μετρήστε τα ψηφία του. Το 835 έχει 3 ψηφία, άρα ο αριθμός των επαναλήψεων είναι 3.

Βήμα 3) Προσδιορίστε τη βάση. Εφόσον αυτή είναι δεκαδική, η βάση είναι το 10.

Βήμα 4) Ξεκινήστε την πρώτη επανάληψη.

α) Πρώτη επανάληψη

Ταξινόμηση κατά το τελευταίο ψηφίο

Στην πρώτη επανάληψη, εξετάζουμε τη μοναδιαία θέση αξίας κάθε στοιχείου.

Βήμα 1) Τροποποιήστε τον ακέραιο αριθμό κατά 10 για να λάβετε τη θέση των στοιχείων. Για παράδειγμα, 623 mod 10 δίνει 3 και 248 mod 10 δίνει 8.

Βήμα 2) Χρησιμοποιήστε την ταξινόμηση με μέτρηση ή κάποια άλλη σταθερή ταξινόμηση για να οργανώσετε τους ακέραιους αριθμούς σύμφωνα με το λιγότερο σημαντικό ψηφίο τους. Από το σχήμα, το 248 εμπίπτει στην 8η κατηγορία, το 623 εμπίπτει στην 3η κατηγορία και ούτω καθεξής.

Μετά την πρώτη επανάληψη, η λίστα μοιάζει τώρα με αυτό.

Λίστα μετά την πρώτη επανάληψη

Η λίστα δεν έχει ακόμη ταξινομηθεί και απαιτεί περισσότερες επαναλήψεις.

β) Δεύτερη επανάληψη

Ταξινόμηση βάσει ψηφίων σε θέση δεκάδων

Σε αυτήν την επανάληψη, λαμβάνουμε υπόψη το ψηφίο στη θέση των δεκάδων για τη διαδικασία ταξινόμησης.

Βήμα 1) Διαιρέστε τους ακέραιους αριθμούς με το 10. Για παράδειγμα, το 248 διαιρούμενο με το 10 δίνει 24.

Βήμα 2) Τροποποιήστε την έξοδο του Βήματος 1 κατά 10. Το 24 mod 10 δίνει 4.

Βήμα 3) Ακολουθήστε το Βήμα 2 από την προηγούμενη επανάληψη.

Μετά τη δεύτερη επανάληψη, η λίστα έχει πλέον ως εξής:

Λίστα μετά τη δεύτερη επανάληψη

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

γ) Τρίτη επανάληψη

Ταξινόμηση με βάση τα ψηφία σε εκατοστά

Για την τελική επανάληψη, θέλουμε να λάβουμε το πιο σημαντικό ψηφίο. Σε αυτήν την περίπτωση, είναι η θέση των εκατοντάδων για κάθε έναν από τους ακέραιους αριθμούς στη λίστα.

Βήμα 1) Διαιρέστε τους ακέραιους αριθμούς με το 100. Για παράδειγμα, το 415 διαιρούμενο με το 100 δίνει 4.

Βήμα 2) Τροποποιήστε το αποτέλεσμα από το Βήμα 1 κατά 10. Η τροποποίηση 4 στο 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 in the jth place
    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 integer
    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 in 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

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

Παραγωγή:

[162, 248, 415, 623, 835]

Ανάλυση Πολυπλοκότητας της Ταξινόμησης Radix

Υπάρχουν δύο τύποι πολυπλοκότητας που πρέπει να ληφθούν υπόψη: η χωρική πολυπλοκότητα και η χρονική πολυπλοκότητα.

• Πολυπλοκότητα χώρου: O(n + b) όπου n είναι το μέγεθος του πίνακα και b είναι η βάση που εξετάζεται.
• Χρονική πολυπλοκότητα: O(d * (n + b)) όπου d είναι ο αριθμός των ψηφίων του μεγαλύτερου στοιχείου στον πίνακα.

Διαστημική πολυπλοκότητα του Radix Sort

Δύο χαρακτηριστικά στα οποία πρέπει να εστιάσετε για την πολυπλοκότητα του χώρου:

• Αριθμός στοιχείων στον πίνακα, n.
• Η βάση που χρησιμοποιείται για την αναπαράσταση των στοιχείων, b.

Μερικές φορές αυτή η βάση μπορεί να είναι μεγαλύτερη από το μέγεθος του πίνακα. Η συνολική πολυπλοκότητα είναι επομένως O(n + b).

Οι ακόλουθες ιδιότητες των στοιχείων στη λίστα μπορούν να καταστήσουν τον χώρο Radix Sort αναποτελεσματικό:

• Στοιχεία με μεγάλο αριθμό ψηφίων.
• Η βάση των στοιχείων είναι μεγάλη, όπως αριθμοί 64 bit.

Χρονική πολυπλοκότητα ταξινόμησης ριζών

Χρησιμοποιώντας την ταξινόμηση με μέτρηση ως υπορουτίνα, κάθε επανάληψη διαρκεί Ο(n + b) χρόνος. Εάν υπάρχουν d επαναλήψεις, γίνεται ο συνολικός χρόνος λειτουργίας Ο(δ * (ν + β))Εδώ, το «O» υποδηλώνει τη συνάρτηση πολυπλοκότητας.

Γραμμικότητα Ταξινόμησης Radix

Η ταξινόμηση Radix είναι γραμμική όταν:

• d είναι σταθερό, όπου d είναι ο αριθμός των ψηφίων του μεγαλύτερου στοιχείου.
• b δεν είναι σημαντικά μεγαλύτερο από n.

Σύγκριση της ταξινόμησης Radix με άλλες μεθόδους ταξινόμησης Algorithms

Η πολυπλοκότητα της Radix Sort εξαρτάται από το μέγεθος του αριθμού. Η καλύτερη περίπτωση και η μέση περίπτωση είναι και οι δύο O(d * (n + b)). Η απόδοση ποικίλλει ανάλογα με την εσωτερική ταξινόμηση — η ταξινόμηση με μέτρηση είναι τυπική, αλλά οποιαδήποτε σταθερή ταξινόμηση λειτουργεί.

Εφαρμογές Αλγόριθμου Ταξινόμησης Radix

Σημαντικές εφαρμογές του Radix Sort είναι:

• Η ταξινόμηση Radix μπορεί να χρησιμοποιηθεί ως αλγόριθμος εύρεσης τοποθεσίας όπου εμπλέκονται μεγάλα εύρη τιμών.
• Χρησιμοποιείται για την κατασκευή ενός πίνακα επιθημάτων στον αλγόριθμο DC3.
• Χρησιμοποιείται σε μηχανήματα διαδοχικής, τυχαίας πρόσβασης όπου οι εγγραφές κλειδώνονται από αναγνωριστικά σταθερού πλάτους.

Συχνές Ερωτήσεις