streamalism.org

1. Pregled

Općeniti algoritmi za sortiranje poput Merge Sort ne pretpostavljaju ulazne podatke, pa ne mogu pobijediti O (n zapisnik n) u najgorem slučaju. Brojanje sortiranja, naprotiv, ima pretpostavku o ulazu što ga čini linearnim algoritmom za sortiranje po vremenu.

U ovom uputstvu upoznat ćemo se s mehanikom Brojačkog sortiranja i zatim ga implementirati u Javu.

2. Brojanje Sortiraj

Brojanje sortiranja, za razliku od većine klasičnih algoritama sortiranja, ne sortira zadani ulaz uspoređivanjem elemenata. Umjesto toga, pretpostavlja da su ulazni elementi n cijeli brojevi u rasponu [0, k]. Kada k = O (n), tada će se izvršiti vrsta brojanja Na) vrijeme.

Stoga imajte na umu da sortiranje ne možemo koristiti kao algoritam za sortiranje opće namjene. Međutim, kada je unos usklađen s ovom pretpostavkom, to je prilično brzo!

2.1. Niz frekvencija

Pretpostavimo da ćemo sortirati ulazni nizs vrijednostima u rasponu [0, 5]:

Prvi, trebali bismo prebrojati pojavu svakog broja u ulaznom nizu. Ako brojanje predstavljamo s nizom C, onda C [i] predstavlja učestalost broja ja u ulaznom nizu:

Na primjer, budući da se 5 u polju za unos pojavljuje 3 puta, vrijednost indeksa 5 jednaka je 3.

Sada s obzirom na niz C, trebali bismo odrediti koliko je elemenata manje ili jednako svakom ulaznom elementu. Na primjer:

• Jedan je element manji ili jednak nuli, ili drugim riječima, postoji samo jedna nulta vrijednost, koja je jednaka C [0]
• Dva su elementa manja ili jednaka jednom, što je jednako C [0] + C [1]
• Četiri su vrijednosti manje ili jednake dvije, što je jednako C [0] + C [1] + C [2]

Pa ako nastavimo računati zbroj n uzastopni elementi u C, možemo znati koliko je elemenata manje ili jednako broju n-1 u ulaznom nizu. U svakom slučaju, primjenom ove jednostavne formule možemo ažurirati C kako slijedi:

2.2. Algoritam

Sada možemo koristiti pomoćni niz C za sortiranje ulaznog polja. Evo kako funkcionira sortiranje brojanja:

• Ponavlja ulazni niz obrnuto
• Za svaki element ja, C [i] - 1 predstavlja mjesto broja ja u razvrstanom nizu. To je zbog činjenice da postoje C [i] elementi manji ili jednaki ja
• Zatim, smanjuje C [i] na kraju svakog kruga

Da bismo sortirali unosni niz uzorka, prvo bismo trebali započeti s brojem 5, jer je to posljednji element. Prema C [5], postoji 11 elemenata koji su manji ili jednaki broju 5.

Dakle, 5 bi trebao biti 11. element u razvrstanom nizu, dakle indeks 10:

Budući da smo premjestili 5 u razvrstani niz, trebali bismo smanjiti C [5]. Sljedeći je element u obrnutom redoslijedu 2. Budući da postoje 4 elementa manja od ili jednaka 2, ovaj broj trebao bi biti četvrti element u razvrstanom nizu:

Slično tome, možemo pronaći pravo mjesto za sljedeći element koji je 0:

Ako nastavimo ponavljati obrnuto i premjestimo svaki element na odgovarajući način, na kraju bismo dobili nešto poput:

3. Brojanje sortiranja - implementacija Jave

3.1. Računanje frekvencijskog niza

Prvo, s obzirom na ulazni niz elemenata i k, trebali bismo izračunati niz C:

int [] countElements (int [] ulaz, int k) {int [] c = novo int [k + 1]; Nizovi.fill (c, 0); za (int i: ulaz) {c [i] + = 1; } za (int i = 1; i <c.length; i ++) {c [i] + = c [i - 1]; } povratak c; }

Raščlanimo potpis metode:

• ulazni predstavlja niz brojeva koje ćemo razvrstati
• The ulazni niz je niz cijelih brojeva u rasponu od [0, k] - dakle k predstavlja maksimalan broj u ulazni
• Tip povrata je niz cijelih brojeva koji predstavljaju C niz

I evo kako countElements metoda djeluje:

• Prvo smo inicijalizirali C niz. Kako sadrži raspon [0, k] k + 1 brojeva, stvaramo niz koji može sadržavati k + 1 brojevi
• Zatim za svaki broj u ulazni, računamo frekvenciju tog broja
• I na kraju, zajedno dodajemo uzastopne elemente kako bismo znali koliko je elemenata manje ili jednako određenom broju

Također, možemo provjeriti je li countElements metoda djeluje prema očekivanjima:

@Test void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected () {int k = 5; int [] ulaz = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] c = CountingSort.countElements (ulaz, k); int [] očekuje se = {1, 2, 4, 6, 8, 11}; assertArrayEquals (očekuje se, c); }

3.2. Sortiranje ulaznog polja

Sada kada možemo izračunati frekvencijski niz, trebali bismo moći razvrstati bilo koji zadani skup brojeva:

int [] sort (int [] input, int k) {int [] c = countElements (input, k); int [] sortirano = novo int [input.length]; for (int i = input.length - 1; i> = 0; i--) {int current = input [i]; sortirano [c [struja] - 1] = struja; c [trenutno] - = 1; } povratak sortiran; }

Evo kako vrsta metoda djeluje:

• Prvo, izračunava C niz
• Zatim ponavlja it ulazni niz obrnuto i za svaki element u ulazni, pronalazi svoje ispravno mjesto u razvrstanom nizu. The i element u ulazni treba biti C [i] th element u sortiranom nizu. Budući da su Java nizovi indeksirani nula, C [i] -1 unos je C [i] th element - na primjer, razvrstano [5] je šesti element u sortiranom nizu
• Svaki put kad pronađemo podudaranje, ono se umanjuje za odgovarajuće C [i] vrijednost

Slično tome, možemo provjeriti je li vrsta metoda djeluje prema očekivanjima:

@Test void sort_GivenAnArray_ShouldSortTheInputAsExpected () {int k = 5; int [] ulaz = {4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}; int [] sortirano = CountingSort.sort (input, k); // Naš algoritam za sortiranje i Java trebaju vratiti isti rezultat Arrays.sort (input); assertArrayEquals (ulaz, sortirano); }

4. Ponovno posjećivanje algoritma sortiranja brojanja

4.1. Analiza složenosti

Većina klasičnih algoritama za sortiranje, poput sortiranja spajanjem, sortira bilo koji unos samo međusobnom usporedbom ulaznih elemenata. Ova vrsta algoritama za sortiranje poznata je pod nazivom vrste usporedbe. U najgorem slučaju, vrste usporedbe trebale bi imati najmanje O(n zapisnik n) sortirati n elementi.

Brojanje sortiranja, s druge strane, ne sortira ulaz uspoređujući ulazne elemente, tako da očito nije algoritam sortiranja usporedbe.

Pogledajmo koliko vremena treba za sortiranje unosa:

• Izračunava C niz u O (n + k) vrijeme: Jednom ponovi ulazni niz s veličinom n u Na) a zatim ponavlja C u U redu) - pa bi to bilo O (n + k) ukupno
• Nakon izračunavanja C, sortira ulaz ponavljanjem ulaznog polja i izvođenjem nekoliko primitivnih operacija u svakoj iteraciji. Dakle, stvarna operacija sortiranja traje Na)

Ukupno brojanje sortiranja traje O (n + k) vrijeme za trčanje:

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

Ako pretpostavimo k = O (n), zatim brojanje algoritam sortiranja sortira ulaz u linearnom vremenu. Za razliku od algoritama za sortiranje opće namjene, sortiranje brojanjem pretpostavlja pretpostavku o ulazu i uzima manje od O(n zapisnik n) donja granica za izvršenje.

4.2. Stabilnost

Prije nekoliko trenutaka postavili smo nekoliko neobičnih pravila o mehanici brojanja sortiranja, ali nikada nismo razjasnili razlog koji stoji iza njih. Da budemo precizniji:

• Zašto bismo ponavljali ulazni niz obrnuto?
• Zašto smanjujemo C [i] svaki put kad ga koristimo?

Ponovimo od početka kako bismo bolje razumjeli prvo pravilo. Pretpostavimo da ćemo sortirati jednostavan niz cijelih brojeva poput sljedećeg:

U prvoj iteraciji trebali bismo pronaći sortirano mjesto za prvih 1:

Dakle, prva pojava broja 1 dobiva posljednji indeks u razvrstanom nizu. Preskačući broj 0, pogledajmo što se događa s drugom pojavom broja 1:

Redoslijed pojavljivanja elemenata iste vrijednosti različit je u ulaznom i sortiranom nizu, tako da algoritam nije stabilan kad ponavljamo od početka.

Što će se dogoditi ako ne umanjimo C [i] vrijednost nakon svake upotrebe? Da vidimo:

Obje pojave broja 1 dobivaju posljednje mjesto u sortiranom nizu. Pa ako ne umanjimo C [i] vrijednost nakon svake upotrebe, mogli bismo izgubiti nekoliko brojeva dok ih razvrstavamo!

5. Zaključak

U ovom smo tutorijalu prvo saznali kako sortiranje brojanja djeluje interno. Tada smo implementirali ovaj algoritam sortiranja u Javu i napisali nekoliko testova kako bismo provjerili njegovo ponašanje. I na kraju, dokazali smo da je algoritam stabilni algoritam sortiranja s linearnom vremenskom složenošću.

Kao i obično, uzorci kodova dostupni su na našem GitHub projektu, zato ga provjerite!