V tej vadnici boste izvedeli, kako deluje sortiranje radix. Prav tako boste našli delovne primere razvrstitve radix v C, C ++, Java in Python.
Radix sort je tehnika razvrščanja, ki razvrsti elemente tako, da najprej razvrsti posamezne števke iste krajevne vrednosti . Nato razvrstite elemente glede na njihov naraščajoči / padajoči vrstni red.
Recimo, da imamo nabor 8 elementov. Najprej bomo razvrstili elemente glede na vrednost mesta enote. Nato bomo razvrstili elemente glede na vrednost desetega mesta. Ta postopek se nadaljuje do zadnjega pomembnega mesta.
Naj bo začetno polje (121, 432, 564, 23, 1, 45, 788). Razvrščeno je glede na radiksno razvrščanje, kot je prikazano na spodnji sliki.
Delovanje Radix Sort
Pred branjem tega članka preglejte sortiranje štetja, ker se sortiranje štetja uporablja kot vmesno sortiranje v radix sortiranju.
Kako deluje Radix Sort?
- Poiščite največji element v matriki, tj. Naj
Xbo število števk vmax.Xse izračuna, ker moramo iti skozi vsa pomembna mesta vseh elementov.
V tem polju(121, 432, 564, 23, 1, 45, 788)imamo največ 788. Ima 3 številke. Zato se mora zanka povzpeti na stotine mest (3-krat). - Zdaj pa pojdite vsakega pomembnega mesta enega za drugim.
Za razvrščanje številk na vsakem pomembnem mestu uporabite katero koli stabilno tehniko razvrščanja. Za to smo uporabili način štetja.
Razvrsti elemente glede na števke enote (X=0).
Uporaba štetja za razvrščanje elementov glede na enoto - Zdaj razvrstite elemente glede na števke na desetine.
Razvrsti elemente glede na desetine - Na koncu razvrstite elemente glede na števke na stotine mest.
Razvrsti elemente glede na stotine mest
Radixov algoritem za razvrščanje
radixSort (matrika) d <- največje število števk v največjem elementu ustvari d vedra velikosti 0-9 za i <- 0, da d razvrsti elemente po številih i-tega mesta z uporabo countingSort countingSort (matrika, d) max <- najdi največji element med elementi d-tega mesta inicializira matriko štetja z vsemi ničlami za j <- 0, da poišče skupno število vsake unikatne številke na d-em mestu elementov in shrani število pri j-tem indeksu v matriko števila za i <- 1 do največjega iskanja kumulativno vsoto in jo shranite v matriko count za j <- velikost do 1 obnovite elemente v matriko zmanjšajte število elementov, obnovljenih za 1
Primeri Python, Java in 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); )
Kompleksnost
Ker je radix sortiranje neprimerjalni algoritem, ima prednosti pred primerjalnimi algoritmi za razvrščanje.
Za sortiranje radix, ki uporablja štetje sorte kot vmesno stabilno sortiranje, je časovna zapletenost O(d(n+k)).
Tu dje številčni cikel in O(n+k)časovna zapletenost štetja.
Tako ima radix razvrščanje linearno časovno zapletenost, ki je boljša kot O(nlog n)pri primerjalnih algoritmih za razvrščanje.
Če vzamemo zelo velika števila številk ali število drugih osnov, kot so 32-bitna in 64-bitna števila, potem lahko deluje v linearnem času, vmesno razvrščanje pa zavzame velik prostor.
Zaradi tega je prostor za razvrščanje radix neučinkovit. To je razlog, zakaj se ta vrsta ne uporablja v knjižnicah programske opreme.
Aplikacije za razvrščanje Radix
Razvrstitev Radix je implementirana v
- Algoritem DC3 (Kärkkäinen-Sanders-Burkhardt) med izdelavo pripone.
- kraji, kjer so številke v velikem obsegu.
