I denne vejledning lærer du, hvordan radix-sortering fungerer. Du finder også arbejdseksempler på radix-sortering i C, C ++, Java og Python.
Radix-sortering er en sorteringsteknik, der sorterer elementerne ved først at gruppere de enkelte cifre med samme stedværdi . Derefter skal du sortere elementerne efter deres stigende / faldende rækkefølge.
Antag, vi har en matrix med 8 elementer. Først sorterer vi elementer baseret på værdien af enhedens sted. Derefter sorterer vi elementer baseret på værdien af det tiende sted. Denne proces fortsætter indtil det sidste vigtige sted.
Lad det oprindelige array være (121, 432, 564, 23, 1, 45, 788). Det er sorteret efter radiksortering som vist i nedenstående figur.
Arbejde af Radix Sort
Gennemgå tællesorteringen, før du læser denne artikel, fordi tællesortering bruges som en mellemliggende sortering i radiksortering.
Hvordan fungerer Radix Sort?
- Find det største element i arrayet, dvs. maks. Lad
Xvære antallet af cifre imax.Xberegnes, fordi vi er nødt til at gennemgå alle de væsentlige steder i alle elementer.
I denne matrix(121, 432, 564, 23, 1, 45, 788)har vi det største nummer 788. Det har 3 cifre. Derfor skal sløjfen gå op til hundreder plads (3 gange). - Gå nu gennem hvert vigtigt sted en efter en.
Brug en hvilken som helst stabil sorteringsteknik til at sortere cifrene på hvert vigtigt sted. Vi har brugt tællesortering til dette.
Sorter elementerne baseret på enhedens stedcifre (X=0).
Brug af tællesortering til at sortere elementer baseret på enhedens sted - Nu skal du sortere elementerne baseret på cifre ti gange.
Sorter elementer baseret på ti-plads - Til sidst skal du sortere elementerne baseret på cifrene hundreder.
Sorter elementer baseret på hundreder
Radix sorteringsalgoritme
radixSort (array) d <- maksimalt antal cifre i det største element oprette d spande med størrelse 0-9 for i <- 0 til d sortere elementerne efter cith sted cifre ved hjælp af countingSort countingSort (array, d) max <- find største element blandt elementerne dth place initialiser tællerarray med alle nuller for j <- 0 til størrelse find det samlede antal af hvert unikke ciffer i dth sted for elementer og gem tællingen ved jth indeks i tæller array for i <- 1 til max find den kumulative sum og gemme den i selve count array for j <- størrelse ned til 1 gendanne elementerne til array reducere antallet af hvert element gendannet med 1
Python, Java og C / C ++ eksempler
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); )
Kompleksitet
Da radiksortering er en ikke-sammenlignende algoritme, har den fordele i forhold til sammenlignende sorteringsalgoritmer.
For radiksorteringen, der bruger tællesortering som en mellemliggende stabil sortering, er tidskompleksiteten O(d(n+k)).
Her der talcyklussen og O(n+k)er tidskompleksiteten af tællesortering.
Radiksortering har således lineær tidskompleksitet, som er bedre end O(nlog n)sammenlignende sorteringsalgoritmer.
Hvis vi tager meget store cifret tal eller antallet af andre baser som 32-bit og 64-bit tal, kan det udføre i lineær tid, men den mellemliggende slags tager stort rum.
Dette gør radix-sorteringsplads ineffektiv. Dette er grunden til, at denne slags ikke bruges i softwarebiblioteker.
Radix Sort applikationer
Radix-sortering implementeres i
- DC3-algoritme (Kärkkäinen-Sanders-Burkhardt), mens du laver et suffiksarray.
- steder, hvor der er tal i store intervaller.
