streamalism.org

1. Áttekintés

Az olyan általános célú rendezési algoritmusok, mint a Merge Sort, nem feltételeznek a bemenetről, így nem tudják legyőzni a O (n log n) a legrosszabb esetben. A Counting Sort ezzel ellentétben feltételezi a bemenetet, ami lineáris időválogató algoritmussá teszi.

Ebben az oktatóanyagban megismerkedünk a Counting Sort mechanikájával, majd megvalósítjuk azt Java-ban.

2. Számlálás rendezése

A rendezés számlálása a legtöbb klasszikus rendezési algoritmussal szemben nem az elemek összehasonlításával rendezi az adott bemenetet. Helyette, feltételezi, hogy a bemeneti elemek azok n egész számok a [0, k]. Mikor k = O (n), akkor a számláló rendezés be fog futni Tovább) idő.

Kérjük, vegye figyelembe, hogy a számlálási rendezést nem használhatjuk általános rendezési algoritmusként. Ha azonban a bemenet igazodik ehhez a feltételezéshez, akkor ez elég gyors!

2.1. Frekvenciatömb

Tegyük fel, hogy egy bemeneti tömböt rendezni fogunkértékekkel a [0, 5] tartományban:

Első, meg kell számolnunk az egyes számok előfordulását a bemeneti tömbben. Ha tömbben ábrázoljuk a számlálást C, azután C [i] a szám gyakoriságát jelenti én a bemeneti tömbben:

Például, mivel az 5 háromszor jelenik meg a bemeneti tömbben, az 5 index értéke megegyezik 3-mal.

Most megadva a tömböt C, meg kellene határoznunk, hogy hány elem kisebb vagy egyenlő az egyes bemeneti elemekkel. Például:

• Egy elem kisebb vagy egyenlő, mint nulla, vagy más szavakkal, csak egy nulla érték van, amely egyenlő C [0]
• Két elem kisebb vagy egyenlő, mint egy, ami egyenlő C [0] + C [1]
• Négy érték kisebb vagy egyenlő kettővel, ami egyenlő C [0] + C [1] + C [2]

Tehát ha folyamatosan számoljuk a n egymást követő elemek C, tudhatjuk, hogy hány elem kisebb, vagy egyenlő a számmal n-1 a bemeneti tömbben. Egyébként ennek az egyszerű képletnek az alkalmazásával frissíthetjük a C az alábbiak szerint:

2.2. Az algoritmus

Most használhatjuk a kiegészítő tömböt C a bemeneti tömb rendezéséhez. Így működik a számlálási rendezés:

• Visszafelé iterálja a bemeneti tömböt
• Minden elemhez én, C [i] -1 a szám helyét jelöli én a rendezett tömbben. Ennek oka az a tény, hogy vannak C [i] kisebb vagy egyenlő elemek én
• Ezután csökkenti a C [i] minden forduló végén

A minta bemeneti tömb rendezése érdekében először az 5-ös számmal kell kezdenünk, mivel ez az utolsó elem. Alapján C [5], van 11 elem kisebb vagy egyenlő az 5 számmal.

Tehát 5-nek kell lennie a 11. elemnek a rendezett tömbben, ezért a 10 index:

Mivel 5-et költöztünk a rendezett tömbhöz, csökkentenünk kell a C [5]. A megfordított sorrend következő eleme a 2. Mivel 4 elem 2-nél kisebb vagy egyenlő, ezért ennek a számnak a rendezett tömb 4. elemének kell lennie:

Hasonlóképpen megtalálhatjuk a megfelelő helyet a következő elemhez, amely 0:

Ha tovább folytatjuk az iterációt és az egyes elemeket megfelelően mozgatjuk, akkor valami ilyesmi lehet:

3. Számlálás rendezése - Java implementáció

3.1. A frekvenciatömb kiszámítása

Először is, adott egy input tömb elemeket és a k, ki kellene számolnunk a tömböt C:

int [] countElements (int [] input, int k) {int [] c = új int [k + 1]; Tömbök.töltés (c, 0); for (int i: input) {c [i] + = 1; } for (int i = 1; i <c.hossz; i ++) {c [i] + = c [i - 1]; } return c; }

Bontjuk le a metódus aláírását:

• bemenet olyan tömböt képvisel, amelyet rendezni fogunk
• A bemenet tömb egész számok tömbje a [0, k] - így k a maximális számot jelenti a bemenet
• A return típus egy egész szám tömb, amely a C sor

És itt van, hogyan countElements a módszer működik:

• Először inicializáltuk a C sor. Ahogy a [0, k] tartomány tartalmazza k + 1 számokat, létrehozunk egy tömböt, amely képes tárolni k + 1 számok
• Ezután a bemenet, kiszámoljuk ennek a számnak a gyakoriságát
• És végül egymás után következő elemeket adunk össze, hogy megtudjuk, hány elem kisebb vagy egyenlő egy adott számmal

Azt is ellenőrizhetjük, hogy a countElements A módszer a várt módon működik:

@Test void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected () {int k = 5; int [] bemenet = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] c = CountingSort.countElements (input, k); int [] várható = {1, 2, 4, 6, 8, 11}; assertArrayEquals (várható, c); }

3.2. A bemeneti tömb rendezése

Most, hogy kiszámíthatjuk a frekvenciatömböt, képesnek kell lennünk az adott számkészlet rendezésére:

int [] sort (int [] input, int k) {int [] c = countElements (input, k); int [] rendezve = új int [bemenet.hossz]; for (int i = bemenet.hossz - 1; i> = 0; i--) {int áram = bemenet [i]; rendezve [c [áram] - 1] = aktuális; c [áram] - = 1; } visszatérés rendezve; }

Itt van, hogyan fajta a módszer működik:

• Először kiszámítja a C sor
• Ezután iterálja a bemenet tömb fordítva és a bemenet, megtalálja a helyes pontját a rendezett tömbben. A ith elem a bemenet legyen az C [i] elem a rendezett tömbben. Mivel a Java tömbök nulla indexelésűek, a C [i] -1 a bejegyzés a C [i] elem - például rendezve [5] a rendezett tömb hatodik eleme
• Valahányszor találunk egyezést, az csökkenti a megfelelőt C [i] érték

Hasonlóképpen ellenőrizhetjük, hogy a fajta A módszer a várt módon működik:

@Test void sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] bemenet = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] sorted = CountingSort.sort (input, k); // A rendezési algoritmusunknak és a Java-nak ugyanazt az eredményt kell adnia, a Arrays.sort (input); assertArrayEquals (bemenet, rendezve); }

4. A számlálási rendezési algoritmus felülvizsgálata

4.1. Komplexitáselemzés

A legtöbb klasszikus rendezési algoritmus, mint az egyesítés rendezése, az adott bemenetet úgy rendezi, hogy csak összehasonlítja a bemeneti elemeket egymással. Az ilyen típusú rendezési algoritmusok néven ismertek összehasonlítás rendezi. A legrosszabb esetben az összehasonlítási fajta legalább O-t vesz fel(n log n) elrendezni n elemek.

A rendezés számlálása viszont nem rendezi a bemenetet a bemeneti elemek összehasonlításával, tehát nyilvánvalóan nem összehasonlító rendezési algoritmus.

Lássuk, mennyi időbe telik a bemenet rendezése:

• Kiszámítja a C tömb be O (n + k) idő: Egyszer megismétli a bemeneti tömböt méretével n ban ben Tovább) majd iterálja a C ban ben Rendben) - így lenne O (n + k) összesen
• Miután kiszámolta a C, úgy rendezi a bemenetet, hogy iterálja a bemeneti tömböt, és minden iterációban végrehajt néhány primitív műveletet. Tehát a tényleges rendezési műveletre van szükség Tovább)

Összességében a rendezés számlálása szükséges O (n + k) a futás ideje:

O (n + k) + O (n) = O (2n + k) = O (n + k)

Ha feltételezzük k = O (n), majd a számláló rendezési algoritmus a bemenetet lineáris időben rendezi. Az általános rendezésű algoritmusokkal szemben a számlálási rendezés feltételezi a bemenetet, és kevesebb, mint az O(n log n) alsó határ végrehajtani.

4.2. Stabilitás

Néhány perccel ezelőtt meghatároztunk néhány különös szabályt a számolás rendezésének mechanikájáról, de soha nem tisztáztuk a mögöttük rejlő okot. Pontosabban:

• Miért kellene iterálni a bemeneti tömböt fordítva?
• Miért csökkentjük a C [i] valahányszor használjuk?

Ismételjük az elejétől kezdve az első szabály jobb megértése érdekében. Tegyük fel, hogy egy egyszerű egész tömböt rendezünk, mint például:

Az első iterációban meg kell találnunk az első 1 rendezett helyét:

Tehát az 1. szám első előfordulása megkapja az utolsó indexet a rendezett tömbben. A 0 szám kihagyásával nézzük meg, mi történik az 1. szám második előfordulásával:

Az azonos értékű elemek megjelenési sorrendje eltér a bemenetben és a rendezett tömbben, ezért az algoritmus nem stabil, ha a kezdetektől iterálunk.

Mi történik, ha nem csökkentjük a C [i] érték minden használat után? Lássuk:

Az 1. szám mindkét előfordulása megszerzi az utolsó helyet a rendezett tömbben. Tehát ha nem csökkentjük a C [i] érték minden használat után, elveszíthetünk néhány számot a rendezés során!

5. Következtetés

Ebben az oktatóanyagban először megtudtuk, hogyan működik a Counting Sort belsőleg. Ezután implementáltuk ezt a rendezési algoritmust a Java-ban, és néhány tesztet írtunk annak viselkedésének igazolására. Végül bebizonyítottuk, hogy az algoritmus stabil, lineáris időbonyolultságú rendezési algoritmus.

Szokás szerint a mintakódok elérhetők a GitHub projektünkön, ezért mindenképpen ellenőrizze!