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

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

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

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

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

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Λίστα ακεραίων προς ταξινόμηση

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

Ακολουθούν τα βήματα για να εκτελέσετε τη διαδικασία ταξινόμησης ριζών:

Βήμα 1) Προσδιορίστε το στοιχείο με τη μέγιστη τιμή στη λίστα. Σε αυτήν την περίπτωση, είναι 835.

Βήμα 2) Υπολογίστε τον αριθμό των ψηφίων του μέγιστου στοιχείου. Το 835 έχει 3 ψηφία ακριβώς.

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

Βήμα 4) Προσδιορίστε τη βάση των στοιχείων. Δεδομένου ότι αυτό είναι ένα δεκαδικό σύστημα, η βάση θα είναι 10.

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Ταξινόμηση κατά το τελευταίο ψηφίο

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

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

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Λίστα μετά την πρώτη επανάληψη

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Ταξινόμηση βάσει ψηφίων σε θέση δεκάδων

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

Βήμα 1) Διαιρέστε τους ακέραιους με το 10. Το 248 διαιρούμενο με το 10 μας δίνει 24.

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

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Λίστα μετά τη δεύτερη επανάληψη

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

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Ταξινόμηση με βάση τα ψηφία σε εκατοντάδες μέρη

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

Βήμα 1) Διαιρούμε τους ακέραιους με το 100… Το 415 διαιρούμενο με το 100 μας δίνει το 4.

Βήμα 2) Mod το αποτέλεσμα από το βήμα 1 με 10. 4 mod 10 μας δίνει ξανά 4.

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

Εργασία Αλγόριθμου Ταξινόμησης Radix
Λίστα μετά την τρίτη επανάληψη

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

Ψευδοκώδικας αλγόριθμου ταξινόμησης ριζών

Εδώ είναι ο ψευδοκώδικας για τον αλγόριθμο ταξινόμησης 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.
  • Χρησιμοποιείται σε ένα μηχάνημα διαδοχικής, τυχαίας πρόσβασης που υπάρχει σε έναν τυπικό υπολογιστή όπου πληκτρολογούνται οι εγγραφές.