Algoritmo di ordinamento radicale nella struttura dei dati

Cos'è l'algoritmo Radix Sort?

Radix Sort è un algoritmo di ordinamento non comparativo. Funziona raggruppandoping le singole cifre degli elementi da ordinare. Viene quindi utilizzata una tecnica di ordinamento stabile per organizzare gli elementi in base alla loro base. Si tratta di un algoritmo di ordinamento lineare.

Il processo di ordinamento coinvolge le seguenti proprietà:

• Si individua l'elemento massimo e si calcola il numero di cifre di tale elemento. Questo fornisce il numero di iterazioni eseguite dal processo di ordinamento.
• Grouping le singole cifre degli elementi nella stessa posizione significativa in ogni iterazione.
• Il gruppoping Il processo inizia dalla cifra meno significativa e termina con la cifra più significativa.
• Ordinamento degli elementi in base alle cifre in quella posizione significativa.
• Mantiene l'ordine relativo degli elementi che hanno lo stesso valore di chiave. Questa proprietà dell'ordinamento Radix lo rende un algoritmo di ordinamento stabile.

L'iterazione finale restituisce un elenco completamente ordinato.

Funzionamento dell'algoritmo Radix Sort

Elenco di numeri interi da ordinare

Ordiniamo l'elenco di numeri interi nella figura precedente in ordine crescente utilizzando l'algoritmo Radix Sort.

Ecco i passaggi per eseguire il processo di ordinamento Radix:

Passo 1) Individua l'elemento massimo nella lista. In questo caso è 835.

Passo 2) Conta le sue cifre. 835 ha 3 cifre, quindi il numero di iterazioni è 3.

Passo 3) Determina la base. Poiché si tratta di un numero decimale, la base è 10.

Passo 4) Avvia la prima iterazione.

a) Prima iterazione

Ordinamento in base all'ultima cifra

Nella prima iterazione, consideriamo il valore posizionale unitario di ciascun elemento.

Passo 1) Si applica il modulo 10 al numero intero per ottenere la cifra delle unità. Ad esempio, 623 mod 10 dà 3 e 248 mod 10 dà 8.

Passo 2) Utilizza l'ordinamento per conteggio o un altro algoritmo di ordinamento stabile per organizzare i numeri interi in base alla loro cifra meno significativa. Come si può vedere nella figura, 248 rientra nell'ottavo gruppo, 623 nel terzo gruppo e così via.

Dopo la prima iterazione, l'elenco ora appare così.

Elenco dopo la prima iterazione

L'elenco non è ancora ordinato e richiede ulteriori iterazioni.

b) Seconda iterazione

Ordinamento in base alle cifre delle decine

In questa iterazione, consideriamo la cifra delle decine per il processo di ordinamento.

Passo 1) Dividi i numeri interi per 10. Ad esempio, 248 diviso 10 dà 24.

Passo 2) Applica il modulo 10 al risultato del passaggio 1. 24 mod 10 dà 4.

Passo 3) Ripeti il ​​passaggio 2 dell'iterazione precedente.

Dopo la seconda iterazione, l'elenco ora si presenta così:

Elenco dopo la seconda iterazione

L'elenco non è ancora completamente ordinato, in quanto non è ancora in ordine crescente.

c) Terza iterazione

Ordinamento in base alle cifre delle centinaia

Per l'ultima iterazione, vogliamo ottenere la cifra più significativa. In questo caso, si tratta della cifra delle centinaia per ciascuno degli interi presenti nell'elenco.

Passo 1) Dividi i numeri interi per 100. Ad esempio, 415 diviso 100 dà 4.

Passo 2) Applica il modulo 10 al risultato del passaggio 1. 4 mod 10 dà 4.

Passo 3) Ripeti il ​​passaggio 3 dell'iterazione precedente.

Elenco dopo la terza iterazione

L'elenco è ora ordinato in ordine crescente. L'ultima iterazione è stata completata e il processo di ordinamento è terminato.

Pseudocodice dell'algoritmo Radix Sort

Ecco lo pseudocodice dell'algoritmo di ordinamento 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++ Programma per implementare l'ordinamento digitale

#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);
}

Produzione:

162 248 415 623 835

Python Programma per l'algoritmo di ordinamento radicale

# 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)

Produzione:

[162, 248, 415, 623, 835]

Analisi della complessità dell'ordinamento Radix

Esistono due tipi di complessità da considerare: la complessità spaziale e la complessità temporale.

• Complessità spaziale: O(n + b) dove n è la dimensione dell'array e b è la base considerata.
• Complessità temporale: O(d * (n + b)) dove d è il numero di cifre dell'elemento più grande nell'array.

Complessità spaziale dell'ordinamento radicale

Due caratteristiche su cui concentrarsi per la complessità spaziale:

• Numero di elementi nell'array, n.
• La base utilizzata per rappresentare gli elementi, b.

A volte questa base può essere maggiore della dimensione dell'array. La complessità complessiva è quindi O(n + b).

Le seguenti proprietà degli elementi presenti nell'elenco possono rendere l'algoritmo Radix Sort inefficiente in termini di spazio:

• Elementi con un gran numero di cifre.
• La base degli elementi è grande, come i numeri a 64 bit.

Complessità temporale dell'ordinamento digitale

Utilizzando l'ordinamento per conteggio come sottoprogramma, ogni iterazione richiede O(n + b) tempo. Se esistono d iterazioni, il tempo di esecuzione totale diventa O(d * (n + b))Qui, “O” denota la funzione di complessità.

Linearità dell'ordinamento radicale

L'ordinamento Radix è lineare quando:

• d è costante, dove d è il numero di cifre dell'elemento più grande.
• b non è significativamente più grande di n.

Confronto tra l'ordinamento Radix e altri algoritmi di ordinamento Algorithms

La complessità dell'algoritmo Radix Sort dipende dalla dimensione del numero. I casi migliori e average-case hanno entrambi una complessità O(d * (n + b)). Le prestazioni variano a seconda dell'algoritmo di ordinamento interno: il counting sort è lo standard, ma qualsiasi algoritmo di ordinamento stabile funziona.

Applicazioni dell'algoritmo Radix Sort

Le principali applicazioni dell'algoritmo Radix Sort sono:

• L'ordinamento Radix può essere utilizzato come algoritmo di localizzazione quando sono coinvolti ampi intervalli di valori.
• Viene utilizzato per costruire un array di suffissi nell'algoritmo DC3.
• Viene utilizzato nelle macchine ad accesso casuale sequenziale, dove i record sono indicizzati da identificatori a larghezza fissa.

DOMANDE FREQUENTI