I den här handledningen lär du dig hur radix-sortering fungerar. Du hittar också arbetsexempel på radix-sortering i C, C ++, Java och Python.
Radix-sortering är en sorteringsteknik som sorterar elementen genom att först gruppera de enskilda siffrorna med samma platsvärde . Sortera sedan elementen efter deras ökande / minskande ordning.
Antag att vi har en rad med åtta element. Först sorterar vi element baserat på värdet på enhetsplatsen. Sedan kommer vi att sortera element baserat på värdet av den tionde platsen. Denna process fortsätter till den sista betydelsefulla platsen.
Låt den ursprungliga matrisen vara (121, 432, 564, 23, 1, 45, 788). Den sorteras efter radiksortering som visas i figuren nedan.
Funktion av Radix Sort
Vänligen gå igenom räknesorteringen innan du läser den här artikeln eftersom räkningssortering används som en mellansortering i radiksortering.
Hur fungerar Radix Sort?
- Hitta det största elementet i matrisen, dvs. max. Låt
Xvara antalet siffror imax.Xberäknas eftersom vi måste gå igenom alla viktiga platser för alla element.
I denna matris(121, 432, 564, 23, 1, 45, 788)har vi det största antalet 788. Den har tre siffror. Därför bör slingan gå upp till hundratals platser (3 gånger). - Gå nu igenom varje betydande plats en efter en.
Använd valfri stabil sorteringsteknik för att sortera siffrorna på varje viktig plats. Vi har använt räkningssortering för detta.
Sortera elementen baserat på enhetsplatsens siffror (X=0).
Använda räknesortering för att sortera element baserat på enhetsplats - Sortera nu elementen baserat på siffror på tiotal.
Sortera element baserat på tiotalsplats - Slutligen sortera elementen baserat på siffrorna på hundratals platser.
Sortera element baserat på hundratals platser
Radix sorteringsalgoritm
radixSort (array) d <- maximalt antal siffror i det största elementet skapa d hinkar av storlek 0-9 för i <- 0 till d sortera elementen efter ith plats siffror med hjälp av countingSort countingSort (array, d) max <- hitta största elementet bland dth-platselementen initialiserar räkneuppsättningen med alla nollor för j <- 0 till storlek hitta det totala antalet för varje unik siffra på dth-platsen för element och spara räkningen vid jth-index i räkningsuppsättningen för i <- 1 till max hitta den kumulativa summan och lagra den i själva räkneuppsättningen för j <- storlek ner till 1 återställ elementen till uppsättningen minska antalet för varje element återställt med 1
Python, Java och C / C ++ exempel
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); )
Komplexitet
Eftersom radiksortering är en icke-jämförande algoritm har den fördelar jämfört med jämförande sorteringsalgoritmer.
För radiksorteringen som använder räkningssortering som en mellanliggande stabil sortering är tidskomplexiteten O(d(n+k)).
Här där talcykeln och O(n+k)är tidskomplexiteten för att räkna sortering.
Således har radiksortering linjär tidskomplexitet som är bättre än O(nlog n)jämförande sorteringsalgoritmer.
Om vi tar väldigt stora siffror eller antalet andra baser som 32-bitars och 64-bitars siffror kan det fungera linjärt, men den mellanliggande typen tar stort utrymme.
Detta gör radix-sorteringsutrymmet ineffektivt. Detta är anledningen till att den här typen inte används i programvarubibliotek.
Radix Sortera applikationer
Radix sort implementeras i
- DC3-algoritm (Kärkkäinen-Sanders-Burkhardt) medan du gör en suffixmatris.
- platser där det finns antal i stora intervall.
