streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megismerhetjük a Radix Sort alkalmazást, elemezhetjük annak teljesítményét és áttekinthetjük a megvalósítását.

Itt összpontosítunk a Radix Sort használatára egész számok rendezésére, de ez nem korlátozódik csak a számokra. Használhatjuk más típusok rendezésére is, mint pl Húr, is.

Az egyszerűség kedvéért arra a tizedesrendszerre fogunk összpontosítani, amelyben a számokat bázisban (radix) fejezzük ki 10.

2. Algoritmus áttekintése

A Radix sort egy rendezési algoritmus, amely a számokat a számjegyük helyzete alapján rendezi. Alapvetően a számjegyek helyértékét használja. Ellentétben a legtöbb más rendezési algoritmussal, például a Merge Sort, Insertion Sort, Bubble Sort, nem hasonlítja össze a számokat.

A Radix rendezés stabil rendezési algoritmust használ alprogramként a számjegyek rendezéséhez. Itt már a számsorozat variációját használtuk szubrutinnak, amely a radix segítségével rendezi a számokat minden helyzetben. A számláló rendezés stabil rendezési algoritmus, és a gyakorlatban is jól működik.

A Radix rendezés úgy működik, hogy szétválogatja a számjegyeket a legkevésbé fontos számtól (LSD) a legjelentősebb számig (MSD). A Radix sort is megvalósíthatjuk az MSD számjegyeinek feldolgozásához.

3. Gyors példa

Nézzük meg, hogyan működik egy példával. Vegyük fontolóra a következő tömböt:

1. iteráció:

Rendezni fogjuk ezt a tömböt az LSD számjegyeinek feldolgozásával és az MSD felé haladással.

Tehát kezdjük a számjegyekkel az egy helyben:

Az első iteráció után a tömb így néz ki:

Ne feledje, hogy a számokat az egy helyben található számjegyek szerint rendezték.

2. iteráció:

Térjünk át a számjegyekre tízes helyen:

A tömb így néz ki:

Látjuk, hogy a 7-es szám elfoglalta az első helyet a tömbben, mivel a tízes helyeken nincs számjegye. Ezt úgy is gondolhatnánk, hogy a tízes helyeken 0 van.

3. iteráció:

Térjünk át a számok százas helyzetére:

Az iteráció után a tömb a következőképpen néz ki:

Az algoritmus itt megáll, minden elemet rendezve.

4. Végrehajtás

Most nézzük meg a megvalósítást.

void sort (int [] számok) {int maximumNumber = findMaximumNumberIn (számok); int számOfDigits = számolNemOfDigitsIn (maximumNumber); int placeValue = 1; while (numberOfDigits--> 0) {ApplyCountingSortOn (számok, placeValue); placeValue * = 10; }}

Az algoritmus úgy működik, hogy megtudja a tömb maximális számát, majd kiszámítja annak hosszát. Ez a lépés segít abban, hogy az alprogramot minden helyértékhez futtassuk.

Például a tömbben [7, 37, 68, 123, 134, 221, 387, 468, 769], a maximális szám 769, hossza 3.

Tehát háromszor ismételjük és alkalmazzuk az alprogramot minden számjegyre:

void applyCountingSortOn (int [] számok, int placeValue) {int tartomány = 10 // decimális rendszer, 0 és 9 közötti számok // ... // kiszámítja a számjegyek gyakoriságát (int i = 0; i <hossz; i ++ ) {int szám = (számok [i] / helyérték)% tartomány; frekvencia [számjegy] ++; } for (int i = 1; i = 0; i--) {int digit = (számok [i] / placeValue)% tartomány; sortedValues ​​[gyakoriság [szám] - 1] = számok [i]; frekvencia [számjegy] -; } System.arraycopy (eredmény, 0, számok, 0, hossz); }

Az alprogramban a radixot használtuk (hatótávolság) számolni az egyes számjegyek előfordulását és növelni a gyakoriságát. Tehát a 0 és 9 közötti tartományban lévő egyes kukáknak van némi értéke a számjegyek gyakorisága alapján. Ezután a frekvenciát használjuk az egyes elemek elhelyezésére a tömbben. Ez abban is segít, hogy minimalizáljuk a tömb rendezéséhez szükséges helyet.

Most teszteljük a módszerünket:

@Teszt nyilvános érvényesség adottUnsortedArray_whenRadixSort_thenArraySorted () {int [] számok = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (számok); int [] számok Rendezve = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (számokSorted, számok); }

5. Radix Sort vs Counting Sort

A szubrutinban a hossza frekvencia tömb 10 (0-9). A Counting Sort esetében nem használjuk a hatótávolság. A hossza frekvencia A tömb lesz a maximális szám a + 1 tömbben. Tehát nem osztjuk őket kukákba, míg a Radix Sort a kukákat rendezi.

A rendezés számlálása elég hatékony, ha a tömb hossza nem sokkal kisebb, mint a tömb maximális értéke, míg a Radix rendezés nagyobb értékeket tesz lehetõvé a tömbben.

6. Komplexitás

A Radix Sort teljesítménye a számok rendezéséhez választott stabil rendezési algoritmustól függ.

Itt a Radix Sort-ot használtuk a tömb rendezéséhez n számok az alapban b. Esetünkben az alap 10. A Counting Sort-ot alkalmaztuk d alkalommal, ahol d a számjegyek számát jelenti. Tehát a Radix Sort időbeli összetettsége válik O (d * (n + b)).

A tér bonyolultsága az O (n + b) mivel itt a Counting Sort variációját használtuk alprogramként.

7. Következtetés

Ebben a cikkben ismertettük a Radix rendezési algoritmust, és bemutattuk annak megvalósítását.

Szokás szerint a kód implementációi elérhetők a Githubon.