streamalism.org

1. Prehľad

Univerzálne triediace algoritmy ako Merge Sort nevytvárajú žiadny predpoklad o vstupe, takže nemôžu prekonať O (n log n) v horšom prípade. Počítanie zoradenia má naopak o vstupe predpoklad, ktorý z neho robí algoritmus lineárneho triedenia času.

V tomto výučbe sa oboznámime s mechanizmami počítania a potom ich implementujeme v Jave.

2. Počítanie Triedenie

Počítanie zoradenia, na rozdiel od väčšiny klasických algoritmov triedenia, netriedi daný vstup porovnaním prvkov. Namiesto toho predpokladá, že vstupné prvky sú n celé čísla v rozsahu [0, k]. Kedy k = O (n), potom sa spustí počítanie O (n) čas.

Upozorňujeme teda, že triedenie počítania nemôžeme použiť ako algoritmus triedenia na všeobecné účely. Ak je však vstup v súlade s týmto predpokladom, je to celkom rýchle!

2.1. Frekvenčné pole

Predpokladajme, že budeme triediť vstupné poles hodnotami v rozsahu [0, 5]:

Najprv, mali by sme počítať výskyt každého čísla vo vstupnom poli. Ak reprezentujeme počítanie s poľom C.potom C [i] predstavuje frekvenciu počtu i vo vstupnom poli:

Napríklad, pretože 5 sa vo vstupnom poli objaví trikrát, hodnota pre index 5 sa rovná 3.

Teraz dané pole C, mali by sme určiť, koľko prvkov je menších alebo rovnakých pre každý vstupný prvok. Napríklad:

• Jeden prvok je menší alebo rovný nule, alebo inými slovami, existuje iba jedna nulová hodnota, ktorá sa rovná C [0]
• Dva prvky sú menšie alebo rovné jednému, čo sa rovná C [0] + C [1]
• Štyri hodnoty sú menšie alebo rovné dvom, čo sa rovná C [0] + C [1] + C [2]

Takže ak budeme stále počítať súčet n po sebe idúce prvky v C, môžeme vedieť, koľko prvkov je menších alebo rovných číslu n-1 vo vstupnom poli. Použitím tohto jednoduchého vzorca každopádne môžeme aktualizovať C. takto:

2.2. Algoritmus

Teraz môžeme použiť pomocné pole C. triediť vstupné pole. Takto funguje počítanie:

• Opakuje iteráciu vstupného poľa
• Pre každý prvok ja, C [i] - 1 predstavuje umiestnenie čísla i v zoradenom poli. Je to tak kvôli skutočnosti, že existujú C [i] prvky menšie alebo rovné i
• Potom zníži hodnotu C [i] na konci každého kola

Aby sme zoradili vzorové vstupné pole, mali by sme najskôr začať od čísla 5, pretože je to posledný prvok. Podľa C [5], existuje 11 prvkov, ktoré sú menšie alebo rovné číslu 5.

5 by teda mal byť 11. prvkom v zoradenom poli, a teda index 10:

Pretože sme presunuli 5 do zoradeného poľa, mali by sme zmenšiť C [5]. Ďalším prvkom v opačnom poradí je 2. Pretože existujú 4 prvky menšie alebo rovné 2, malo by toto číslo byť 4. prvkom v zoradenom poli:

Podobne môžeme nájsť správne miesto pre ďalší prvok, ktorý je 0:

Ak budeme pokračovať v iterácii v opačnom poradí a vhodne posúvať každý prvok, skončilo by to niečo ako:

3. Počítanie zoradenie - implementácia Java

3.1. Výpočet frekvenčného poľa

Najprv je zadané vstupné pole prvkov a k, mali by sme vypočítať pole C:

int [] countElements (int [] vstup, int k) {int [] c = nový int [k + 1]; Polia.vyplnenie (c, 0); pre (int i: vstup) {c [i] + = 1; } for (int i = 1; i <c.length; i ++) {c [i] + = c [i - 1]; } návrat c; }

Poďme rozdeliť podpis metódy:

• vstup predstavuje pole čísel, ktoré ideme triediť
• The vstup pole je pole celých čísel v rozsahu [0, k] - tak k predstavuje maximálny počet v vstup
• Návratový typ je pole celých čísel predstavujúce C. pole

A tu je príklad countElements metóda funguje:

• Najskôr sme inicializovali C. pole. Pretože rozsah [0, k] obsahuje k + 1 čísla, vytvárame pole schopné obsahovať k + 1 čísla
• Potom pre každé číslo v vstup, počítame frekvenciu tohto čísla
• A nakoniec pridávame po sebe idúce prvky, aby sme vedeli, koľko prvkov je menej alebo rovnaké ako konkrétne číslo

Môžeme tiež overiť, či countElements metóda funguje podľa očakávania:

@Test void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExected () {int k = 5; int [] vstup = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] c = CountingSort.countElements (vstup, k); int [] očakávané = {1, 2, 4, 6, 8, 11}; assertArrayEquals (očakávané, c); }

3.2. Triedenie vstupného poľa

Teraz, keď môžeme vypočítať frekvenčné pole, by sme mali byť schopní triediť ľubovoľnú danú množinu čísel:

int [] sort (int [] vstup, int k) {int [] c = countElements (vstup, k); int [] triedené = nové int [input.length]; for (int i = input.length - 1; i> = 0; i--) {int current = input [i]; triedené [c [aktuálne] - 1] = aktuálne; c [aktuálny] - = 1; } návrat zoradený; }

Tu je postup, ako triediť metóda funguje:

• Najskôr to spočíta C. pole
• Potom iteruje vstup pole v opačnom poradí a pre každý prvok v vstup, nájde svoje správne miesto v zoradenom poli. The i prvok v vstup by mala byť C [i] th prvok v zoradenom poli. Pretože polia Java majú nulový index, pole C [i] -1 vstup je C [i] th prvok - napríklad zoradené [5] je šiestym prvkom v zoradenom poli
• Zakaždým, keď nájdeme zhodu, zmenší zodpovedajúcu hodnotu C [i] hodnotu

Podobne môžeme overiť, či triediť metóda funguje podľa očakávania:

@Test void sort_GivenAnArray_ShouldSortTheInputAsExected () {int k = 5; int [] vstup = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] triedené = CountingSort.sort (vstup, k); // Náš triediaci algoritmus a Java by mali vrátiť rovnaký výsledok Arrays.sort (vstup); assertArrayEquals (vstup, zoradené); }

4. Prehodnotenie algoritmu zoradenia počítania

4.1. Analýza zložitosti

Väčšina klasických algoritmov triedenia, ako napríklad zlúčenie, zoraďuje akýkoľvek zadaný vstup iba porovnaním vstupných prvkov navzájom. Tieto typy triediacich algoritmov sú známe ako porovnávacie druhy. V najhoršom prípade by porovnávacie druhy mali trvať minimálne O(n log n) triediť n prvkov.

Na druhej strane funkcia Counting Sort netriedi vstup porovnaním vstupných prvkov, takže zjavne nejde o algoritmus porovnania triedenia.

Pozrime sa, koľko času zaberie triedenie vstupu:

• Počíta sa C. pole v O (n + k) čas: Raz iteruje vstupné pole s veľkosťou n v O (n) a potom iteruje C. v O (k) - tak to by bolo O (n + k) spolu
• Po výpočte C, triedi vstup iteráciou vstupného poľa a vykonaním niekoľkých primitívnych operácií v každej iterácii. Skutočná operácia triedenia teda trvá O (n)

Celkovo počítanie trvá O (n + k) čas spustenia:

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

Ak predpokladáme k = O (n), potom algoritmus počítania triedenia triedi vstup v lineárnom čase. Na rozdiel od univerzálnych algoritmov triedenia počíta spôsob triedenia predpoklad o vstupe a trvá menej ako O(n log n) dolná hranica vykonania.

4.2. Stabilita

Pred niekoľkými okamihmi sme stanovili niekoľko zvláštnych pravidiel týkajúcich sa mechaniky počítania druhov, ale nikdy sme nevyjasnili dôvod, ktorý za nimi stojí. Aby som bol konkrétnejší:

• Prečo by sme mali iterovať vstupné pole opačne?
• Prečo znižujeme C [i] zakaždým, keď to používame?

Poďme iterovať od začiatku, aby sme lepšie pochopili prvé pravidlo. Predpokladajme, že budeme triediť jednoduché pole celých čísel, ako je toto:

V prvej iterácii by sme mali nájsť zoradené umiestnenie pre prvú 1:

Takže prvý výskyt čísla 1 získa posledný index v zoradenom poli. Ak preskočíte číslo 0, pozrime sa, čo sa stane s druhým výskytom čísla 1:

Poradie vzhľadu prvkov s rovnakou hodnotou je odlišné vo vstupnom a zoradenom poli, takže algoritmus nie je stabilný, keď iterujeme od začiatku.

Čo sa stane, ak neznížime C [i] hodnota po každom použití? Pozrime sa:

Oba výskyty čísla 1 dostávajú posledné miesto v zoradenom poli. Takže ak neznížime C [i] hodnotu po každom použití, mohli by sme pri ich triedení potenciálne stratiť niekoľko čísel!

5. Záver

V tomto tutoriáli sme sa najskôr dozvedeli, ako interne funguje počítanie zoradenia. Potom sme implementovali tento algoritmus triedenia v Jave a napísali niekoľko testov na overenie jeho správania. A nakoniec sme dokázali, že algoritmus je stabilný algoritmus triedenia s lineárnou časovou zložitosťou.

Vzorové kódy sú ako obvykle k dispozícii v našom projekte GitHub, takže si ich určite pozrite!