Algoritmo di ordinamento radicale nella struttura dei dati

Cos'è l'algoritmo Radix Sort?

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

Il processo di ordinamento coinvolge le seguenti proprietà:

• Trovare l'elemento massimo e acquisire il numero di cifre di quell'elemento. Ci dà il numero di iterazioni che seguirà il processo di ordinamento.
• Raggruppare le singole cifre degli elementi nella stessa posizione significativa in ciascuna iterazione.
• Il processo di raggruppamento inizierà dalla cifra meno significativa e terminerà con la cifra più significativa.
• Ordinamento degli elementi in base alle cifre in quella posizione significativa.
• Mantenimento dell'ordine relativo degli elementi che hanno lo stesso valore chiave. Questa proprietà del radix sort lo rende un ordinamento stabile.

L'iterazione finale ci fornirà un elenco completamente ordinato.

Funzionamento dell'algoritmo Radix Sort

Proviamo a ordinare l'elenco di numeri interi nella figura sopra in ordine crescente utilizzando l'algoritmo Radix Sort.

Ecco i passaggi per eseguire il processo di ordinamento radicale:

Passo 1) Identificare l'elemento con il valore massimo nell'elenco. In questo caso è 835.

Passo 2) Calcolare il numero di cifre dell'elemento massimo. 835 ha esattamente 3 cifre.

Passo 3) Determinare il numero di iterazioni in base al passaggio 2. 835 ha 3 cifre, il che significa che il numero di iterazioni sarà 3.

Passo 4) Determinare la base degli elementi. Poiché si tratta di un sistema decimale, la base sarà 10.

Passo 5) Avvia la prima iterazione.

a) Prima iterazione

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

Passo 1) Modifica il numero intero per 10 per ottenere il posto unitario degli elementi. Ad esempio, 623 mod 10 ci dà il valore 3 e 248 mod 10 ci dà 8.

Passo 2) Utilizzare l'ordinamento di conteggio o qualsiasi altro ordinamento stabile per organizzare gli interi in base alla cifra meno significativa. Come si vede dalla figura, 248 cadranno nell'ottavo secchio. 8 cadranno sul 623° secchio e così via.

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

Come puoi vedere dalla figura sopra, l'elenco non è ancora ordinato e richiede più iterazioni per essere completamente ordinato.

b) Seconda iterazione

In questa iterazione, considereremo la cifra 10^th posto per il processo di smistamento.

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

Passo 2) Modifica l'output del passaggio 1 per 10. 24 mod 10 ci dà 4.

Passo 3) Seguire il passaggio 2 dell'iterazione precedente.

Dopo la seconda iterazione, l'elenco ora appare così

Puoi vedere dalla figura sopra che l'elenco non è ancora completamente ordinato poiché non è ancora in ordine crescente.

c) Terza iterazione

Per l'iterazione finale, vogliamo ottenere la cifra più significativa. In questo caso sono i 100^th posto per ciascuno dei numeri interi nell'elenco.

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

Passo 2) Modifica il risultato del passaggio 1 con 10. 4 mod 10 ci dà di nuovo 4.

Passo 3) Seguire il passaggio 3 dell'iterazione precedente.

Come possiamo vedere, l'elenco è ora ordinato in ordine crescente. L'iterazione finale è stata completata e il processo di ordinamento è terminato.

Pseudocodice dell'algoritmo Radix Sort

Ecco lo pseudo-codice per l'algoritmo Radix Sort

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

Produzione:

162 248 415 623 835

Python Programma per l'algoritmo di ordinamento radicale

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

Produzione:

[162,248,415,623,835]

Analisi della complessità di Radix Sort

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à dello spazio

• Numero di elementi nell'array, n.
• La base 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 nell'elenco possono rendere inefficiente lo spazio di ordinamento digitale:

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

Complessità temporale dell'ordinamento digitale

È possibile utilizzare l'ordinamento del conteggio come una subroutine, poiché richiederà ogni iterazioneeO(n+b) tempo. Se esistono d iterazioni, il tempo di esecuzione totale diventa O(d*(n+b)). Qui, "O" indica la funzione di complessità.

Linearità dell'ordinamento radicale

Radix Sort è lineare quando

• d è costante, dove d è il numero di cifre dell'elemento più grande.
• b non è più grande in larga misura rispetto a n.

Confronti di Radix Sort con altri algoritmi comparativi

Come abbiamo visto, la complessità del Radix sort si basa sulla dimensione di una parola o di un numero. Avrà la stessa complessità per i casi medi e migliori. E questo è O(d*(n+b)). Inoltre, differisce in base alla tecnica di ordinamento che usi nel mezzo. Ad esempio, puoi usare counting sort o quick sort per l'algoritmo di ordinamento intermedio all'interno del Radix sort.

Applicazioni dell'algoritmo Radix Sort

Importanti applicazioni di Radix Sort sono:

• Radix Sort può essere utilizzato come algoritmo di ricerca della posizione in cui vengono utilizzati ampi intervalli di valori.
• Viene utilizzato nella costruzione di un array di suffissi nell'algoritmo DC3.
• Viene utilizzato in una macchina sequenziale ad accesso casuale presente in un tipico computer in cui vengono codificati i record.