În acest tutorial, veți afla cum funcționează sortarea radix. De asemenea, veți găsi exemple de lucru de sortare radix în C, C ++, Java și Python.
Sortarea Radix este o tehnică de sortare care sortează elementele grupând mai întâi cifrele individuale cu aceeași valoare de poziție . Apoi, sortați elementele în funcție de ordinea lor crescătoare / descrescătoare.
Să presupunem că avem o matrice de 8 elemente. În primul rând, vom sorta elemente pe baza valorii locului unității. Apoi, vom sorta elemente pe baza valorii locului zecelea. Acest proces continuă până la ultimul loc semnificativ.
Să fie matricea inițială (121, 432, 564, 23, 1, 45, 788). Este sortat în funcție de sortarea radix așa cum se arată în figura de mai jos.
Funcționarea Radix Sort
Vă rugăm să parcurgeți sortarea de numărare înainte de a citi acest articol, deoarece sortarea de numărare este utilizată ca sortare intermediară în sortarea radix.
Cum funcționează sortarea Radix?
- Găsiți cel mai mare element din matrice, adică max. Fie
Xnumărul de cifre dinmax.Xeste calculat deoarece trebuie să parcurgem toate locurile semnificative ale tuturor elementelor.
În această matrice(121, 432, 564, 23, 1, 45, 788), avem cel mai mare număr 788. Are 3 cifre. Prin urmare, bucla ar trebui să urce la sute de locuri (de 3 ori). - Acum, parcurgeți fiecare loc semnificativ unul câte unul.
Utilizați orice tehnică stabilă de sortare pentru a sorta cifrele în fiecare loc semnificativ. Pentru aceasta am folosit sortare de numărare.
Sortați elementele pe baza cifrelor poziției unității (X=0).
Utilizarea sortării numărării pentru a sorta elementele în funcție de locul unității - Acum, sortați elementele pe baza cifrelor la zeci.
Sortați elementele în funcție de locul zecilor - În cele din urmă, sortați elementele pe baza cifrelor la sute.
Sortați elementele în funcție de locul sutelor
Algoritmul de sortare Radix
radixSort (array) d <- numărul maxim de cifre din cel mai mare element creați d găleți de dimensiunea 0-9 pentru i <- 0 pentru a sorta elementele în funcție de cifrele ith loc folosind countingSort countingSort (array, d) max <- găsiți cel mai mare element dintre elementele locului al zecelea inițializează matricea de numărare cu toate zerourile pentru j <- 0 la dimensiune, găsește numărul total al fiecărei cifre unice în locul al zecelea al elementelor și stochează numărul la indexul j în matrice de numărare pentru i <- 1 până la găsirea maximă suma cumulativă și stocați-o în matrice de numărare în sine pentru j <- dimensiunea până la 1 restabiliți elementele la matrice numărul de scăderi al fiecărui element restaurat cu 1
Exemple Python, Java și 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); )
Complexitate
Deoarece sortarea radix este un algoritm non-comparativ, are avantaje față de algoritmii de sortare comparativă.
Pentru sortarea radix care folosește sortarea de numărare ca sortare stabilă intermediară, complexitatea timpului este O(d(n+k)).
Aici deste ciclul numeric și O(n+k)este complexitatea timpului de numărare a sortării.
Astfel, sortarea radix are o complexitate liniară a timpului, care este mai bună decât O(nlog n)a algoritmilor de sortare comparativă.
Dacă luăm numere de cifre foarte mari sau numărul altor baze, cum ar fi numerele de 32 de biți și 64 de biți, atunci acesta poate funcționa în timp liniar, totuși sortarea intermediară ocupă spațiu mare.
Acest lucru face ca spațiul de sortare radix să fie ineficient. Acesta este motivul pentru care acest tip nu este utilizat în bibliotecile software.
Aplicații de sortare Radix
Sortarea Radix este implementată în
- Algoritmul DC3 (Kärkkäinen-Sanders-Burkhardt) în timp ce realizați o matrice de sufixe.
- locuri unde există numere în intervale mari.
