„Radix“ rūšiavimo algoritmas

Turinys

Kaip veikia „Radix“ rūšiavimas?
„Radix“ rūšiavimo algoritmas
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
Sudėtingumas
„Radix“ rūšiavimo programos

Šioje pamokoje sužinosite, kaip veikia radix rūšiavimas. Taip pat rasite veikiančių radix rūšiavimo pavyzdžių C, C ++, Java ir Python.

„Radix sort“ yra rūšiavimo technika, kuri rūšiuoja elementus pirmiausia sugrupuodama atskirus tos pačios vietos vertės skaitmenis . Tada surūšiuokite elementus pagal jų didėjimo / mažėjimo tvarką.

Tarkime, mes turime 8 elementų masyvą. Pirma, mes rūšiuosime elementus pagal vietos vieneto vertę. Tada mes rūšiuosime elementus pagal dešimtosios vietos vertę. Šis procesas tęsiasi iki paskutinės reikšmingos vietos.

Tegul yra pradinis masyvas (121, 432, 564, 23, 1, 45, 788). Jis rūšiuojamas pagal radix rūšiavimą, kaip parodyta toliau pateiktame paveikslėlyje.

„Radix Sort“ darbas

Prieš perskaitydami šį straipsnį, pereikite prie skaičiavimo rūšiavimo, nes skaičiavimo rūšiavimas naudojamas kaip tarpinis rūšiavimas pagal radix rūšį.

Kaip veikia „Radix“ rūšiavimas?

Raskite didžiausią masyvo elementą, ty maks. Leisti Xbūti skaitmenų skaičius max. Xyra apskaičiuojamas, nes turime pereiti visas reikšmingas visų elementų vietas.
Šiame masyve (121, 432, 564, 23, 1, 45, 788)turime didžiausią skaičių 788. Jis turi 3 skaitmenis. Todėl kilpa turėtų pakilti į šimtus vietų (3 kartus).
Dabar eikite po kiekvieną reikšmingą vietą po vieną.
Norėdami rūšiuoti skaitmenis kiekvienoje reikšmingoje vietoje, naudokite bet kurią stabilią rūšiavimo techniką. Tam naudojome skaičiavimo rūšiavimą.
Rūšiuoti elementus pagal vieneto vietos skaitmenis ( X=0). Skaičiavimo rūšiavimo naudojimas elementams rūšiuoti pagal vietos vienetą
Dabar rūšiuokite elementus pagal skaitmenis dešimtyse. Rūšiuoti elementus pagal dešimčių vietą
Galiausiai rūšiuokite elementus pagal skaitmenis šimtuose vietų. Rūšiuoti elementus pagal šimtus vietų

„Radix“ rūšiavimo algoritmas

 radixSort (masyvas) d <- didžiausias skaitmenų skaičius didžiausiame elemente sukuria d 0 0–9 dydžio kibirus, skirtus i <- 0, kad elementai būtų rūšiuojami pagal „i“ vietos skaitmenis, naudojant countingSort countingSort (masyvas, d) max <- rasti didžiausias elementas tarp d-osios vietos elementų inicijuoja skaičiaus masyvą su visais nuliais, kai j <- 0, kad rastumėte dydį, suraskite bendrą kiekvieno unikalaus skaitmens skaičių d-ojoje elementų vietoje ir išsaugokite skaičių j-jame indekse skaičiaus masyve i kaupiamąją sumą ir saugokite ją pačiame skaičiaus masyve j <- dydis iki 1 atstatyti elementus, kad masyvas sumažintų kiekvieno atkurto elemento skaičių 1

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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); )

Sudėtingumas

Kadangi radikso rūšiavimas yra nelyginamasis algoritmas, jis turi pranašumų, palyginti su lyginamojo rūšiavimo algoritmais.

Radix rūšiavimui, kuris naudoja skaičiavimo rūšį kaip tarpinę stabilią rūšiavimą, laiko sudėtingumas yra O(d(n+k)).

Čia dyra skaičių ciklas ir O(n+k)laiko skaičiavimo rūšiavimo sudėtingumas.

Taigi radix rūšiavimas yra tiesinio laiko sudėtingumo, kuris yra geresnis nei O(nlog n)lyginamųjų rūšiavimo algoritmų.

Jei imsime labai didelius skaitmenis arba kitų bazių, tokių kaip 32 bitų ir 64 bitų, skaičių, tada jis gali būti atliekamas linijiniu laiku, tačiau tarpinė rūšis užima daug vietos.

Dėl to radix rūšiavimo erdvė yra neefektyvi. Tai yra priežastis, kodėl ši rūšis nenaudojama programinės įrangos bibliotekose.