Ebben az oktatóanyagban megtudhatja, hogyan működik a radix rendezés. Emellett a radix rendezésének működő példáit is megtalálja C, C ++, Java és Python nyelven.
Radix rendezés válogatásra, hogy rendezi az elemeket először csoportosítása az egyes számjegyek az azonos helyi érték . Ezután rendezze az elemeket növekvő / csökkenő sorrend szerint.
Tegyük fel, hogy van egy 8 elemből álló tömbünk. Először az egység helyének értéke alapján rendezünk elemeket. Ezután elemeket rendezünk a tizedik hely értéke alapján. Ez a folyamat az utolsó jelentős helyig tart.
Legyen a kezdeti tömb (121, 432, 564, 23, 1, 45, 788). Radix rendezés szerint van rendezve, az alábbi ábra szerint.
A Radix Sort működése
Kérjük, olvassa el a számlálási rendet, mielőtt elolvassa ezt a cikket, mert a számláló rendezés közbenső rendezésként szolgál a radix rendezésben.
Hogyan működik a Radix Sort?
- Keresse meg a tömb legnagyobb elemét, azaz max. Legyen
Xa számjegyek számamax.Xazért számítunk, mert minden elem összes jelentős helyén át kell mennünk.
Ebben a tömbben(121, 432, 564, 23, 1, 45, 788)a legnagyobb a 788. szám. 3 számjegyből áll. Ezért a ciklusnak több száz helyre kell felmennie (háromszor). - Most egyenként járja végig az összes jelentős helyet.
Használjon bármilyen stabil rendezési technikát a számjegyek rendezéséhez minden jelentős helyen. Ehhez számolási rendet használtunk.
Rendezze az elemeket az egység helyjegyei (X=0) alapján.
A számláló rendezés használata az elemek hely szerinti rendezéséhez - Most rendezze az elemeket tízes számjegyek alapján.
Rendezzen elemeket tízes helyek alapján - Végül rendezze az elemeket a számjegyek alapján több száz helyen.
Rendezzen elemeket több száz hely alapján
Radix rendezési algoritmus
radixSort (tömb) d <- a legnagyobb elemben lévő számjegyek maximális száma hozhat létre 0-9 méretű d vödröt i <- 0 számára, hogy d az elemeket az i-edik számjegyek szerint rendezze a countingSort countingSort (tömb, d) max <- keresés legnagyobb elem a d-hellyel rendelkező elemek között inicializálja a számlálási tömböt az összes nullával a j <- 0 méretre, keresse meg az egyes egyedi számok összes számát az elemek d-edik helyén, és tárolja a számot a j-dik indexben a count tömbben az i <- 1-től max-ig a kumulatív összeget, és tárolja magát a számláló tömbben j <- méretig 1-ig visszaállítva az elemeket tömbcsökkenés-számként az egyes elemekkel 1-gyel visszaállítva
Példák Python, Java és 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); )
Bonyolultság
Mivel a radix rendezés nem összehasonlító algoritmus, előnyei vannak az összehasonlító rendezési algoritmusokkal szemben.
Az a radix rendezés, amely a számlálási rendezést közbenső stabil rendezésként használja, az idő bonyolultsága O(d(n+k)).
Itt da számciklus és O(n+k)a számlálás rendezésének időbeli összetettsége.
Így a radix rendezés lineáris komplexitással rendelkezik, ami jobb, mint O(nlog n)az összehasonlító rendezési algoritmusoké.
Ha nagyon nagy számjegyű számokat vagy más bázisok számát vesszük figyelembe, például a 32 bites és a 64 bites számokat, akkor lineáris időben is teljesíthet, azonban a köztes rendezés nagy helyet foglal el.
Ez a radix rendezési teret hatástalanná teszi. Ez az oka annak, hogy ezt a fajtát nem használják a szoftverkönyvtárakban.
Radix Sort Applications
A Radix rendezés a
- DC3 algoritmus (Kärkkäinen-Sanders-Burkhardt) utótag tömb készítése közben.
- olyan helyek, ahol nagy tartományokban vannak számok.
