In questo tutorial imparerai come funziona l'ordinamento digitale. Inoltre, troverai esempi funzionanti di ordinamento digitale in C, C ++, Java e Python.
L'ordinamento digitale è una tecnica di ordinamento che ordina gli elementi raggruppando prima le singole cifre dello stesso valore di posizione . Quindi, ordina gli elementi in base al loro ordine crescente / decrescente.
Supponiamo di avere un array di 8 elementi. Per prima cosa, ordineremo gli elementi in base al valore della posizione dell'unità. Quindi, ordineremo gli elementi in base al valore del decimo posto. Questo processo va avanti fino all'ultimo posto significativo.
Sia l'array iniziale (121, 432, 564, 23, 1, 45, 788). Viene ordinato in base all'ordinamento digitale come mostrato nella figura seguente.
Funzionamento di Radix Sort
Si prega di esaminare l'ordinamento conteggio prima di leggere questo articolo perché l'ordinamento conteggio viene utilizzato come ordinamento intermedio nell'ordinamento digitale.
Come funziona Radix Sort?
- Trova l'elemento più grande nell'array, cioè max. Sia
Xil numero di cifre inmax.Xè calcolato perché dobbiamo attraversare tutti i luoghi significativi di tutti gli elementi.
In questo array(121, 432, 564, 23, 1, 45, 788), abbiamo il numero più grande 788. Ha 3 cifre. Pertanto, il ciclo dovrebbe salire fino a centinaia di posizioni (3 volte). - Ora, passa attraverso ogni luogo significativo uno per uno.
Usa una tecnica di ordinamento stabile per ordinare le cifre in ogni punto significativo. Abbiamo usato l'ordinamento conteggio per questo.
Ordina gli elementi in base alle cifre del luogo dell'unità (X=0).
Utilizzo dell'ordinamento conteggio per ordinare gli elementi in base alla posizione dell'unità - Ora, ordina gli elementi in base alle cifre al posto delle decine.
Ordina gli elementi in base alle decine - Infine, ordina gli elementi in base alle cifre in centinaia.
Ordina gli elementi in base a centinaia di posizioni
Algoritmo di ordinamento della radice
radixSort (array) d <- numero massimo di cifre nell'elemento più grande crea d bucket di dimensione 0-9 per i <- 0 to d ordina gli elementi in base alle cifre della posizione utilizzando countingSort countingSort (array, d) max <- find elemento più grande tra gli elementi d-esimo posto inizializza l'array di conteggio con tutti zeri per j <- 0 per la dimensione trova il conteggio totale di ogni cifra univoca al posto d-esimo degli elementi e memorizza il conteggio all'indice jth nell'array di conteggio per i <- 1 a max find la somma cumulativa e la memorizza nel count array stesso per j <- dimensione fino a 1 ripristina gli elementi nell'array diminuisce il conteggio di ogni elemento ripristinato di 1
Esempi di Python, Java e 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); )
Complessità
Poiché l'ordinamento digitale è un algoritmo non comparativo, presenta vantaggi rispetto agli algoritmi di ordinamento comparativo.
Per l'ordinamento digitale che utilizza l'ordinamento conteggio come ordinamento stabile intermedio, la complessità temporale è O(d(n+k)).
Ecco dil ciclo numerico e O(n+k)la complessità temporale del conteggio dell'ordinamento.
Pertanto, l'ordinamento digitale ha una complessità temporale lineare che è migliore O(nlog n)degli algoritmi di ordinamento comparativo.
Se prendiamo numeri di cifre molto grandi o il numero di altre basi come numeri a 32 bit e 64 bit, può funzionare in tempo lineare, tuttavia l'ordinamento intermedio richiede molto spazio.
Ciò rende inefficiente lo spazio di ordinamento digitale. Questo è il motivo per cui questo tipo non viene utilizzato nelle librerie software.
Radix Sort Applications
L'ordinamento digitale è implementato in
- Algoritmo DC3 (Kärkkäinen-Sanders-Burkhardt) durante la creazione di un array di suffissi.
- luoghi in cui sono presenti numeri in ampi intervalli.
