streamalism.org

1. Uvod

U ovom ćemo članku zaroniti u algoritam sortiranja segmenata. Krenut ćemo s brzim malo teorije, prije rada na implementaciji Jave uz jedinstveno testiranje našeg rješenja. Napokon ćemo pogledajte vremensku složenost sortiranja kanta.

2. Teorija sortiranja kante

Sortiranje u kantama, ponekad poznato i kao sortiranje u kante, specifičan je algoritam sortiranja. Razvrstavanje djeluje distribucijom elemenata koje želimo razvrstati u nekoliko pojedinačno razvrstanih segmenata. Na taj način možemo smanjiti broj usporedbi između elemenata i pomoći smanjiti vrijeme sortiranja.

Pogledajmo na brzinu koraci potrebni za izvršavanje sortiranja segmenta:

1. Postavite niz naših prvotno praznih segmenata
2. Distribuirajte naše elemente u odgovarajuće kante
3. Poredaj svaku kantu
4. Spojite razvrstane segmente kako biste stvorili cjelovit popis

3. Implementacija Jave

Iako ovaj algoritam nije specifičan za jezik, sortiranje ćemo implementirati u Javi. Idemo korak po korak kroz gornji popis i napišite kod za sortiranje popisa cijelih brojeva.

3.1. Postavljanje kante

Prvo, mi treba odrediti algoritam raspršivanja da odlučimo koji će se od naših elemenata smjestiti u koju kantu:

private int hash (int i, int max, int numberOfBuckets) {return (int) ((double) i / max * (numberOfBuckets - 1)); }

S definiranom našom hash metodom, sada to možemo navedite broj spremnika kao kvadratni korijen veličine popisa ulaza:

konačni int numberOfBuckets = (int) Math.sqrt (InitialList.size ()); Popis kante = novi ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (novi ArrayList ()); }

Konačno, trebamo kratku metodu za određivanje maksimalnog cijelog broja na našem popisu unosa:

private int findMax (ulaz s popisa) {int m = Integer.MIN_VALUE; for (int i: input) {m = Math.max (i, m); } povratak m; }

3.2. Distribucija elemenata

Sad kad imamo definirane kante, možemo distribuiramo svaki element našeg popisa unosa u odgovarajući segment pomoću hash metoda:

int max = findMax (InitialList); for (int i: InitialList) {buckets.get (hash (i, max, numberOfBuckets)). add (i); } 

3.3. Sortiranje pojedinačnih segmenata

S definiranim segmentima i punim cijelih brojeva, poslužimo se a Usporednik da ih razvrsta:

Usporednik za usporedbu = Comparator.naturalOrder (); za (Popis segmenta: segmenata) {bucket.sort (komparator); }

3.4. Spajanje naših kanta

Napokon, moramo sakupiti kante kako bismo stvorili jedinstveni popis. Budući da su naša segmenti razvrstani, trebamo samo jednom petlje proći kroz svaki segment i dodati elemente glavnom popisu:

Popis sortedArray = novi LinkedList (); za (Popis segmenta: kante) {sortedArray.addAll (segmenta); } povratak sortedArray;

4. Testiranje našeg koda

Nakon što je naša implementacija dovršena, napišimo brzi unit test kako bismo bili sigurni da radi kako se očekuje:

Sortiranje BucketSorter = novo IntegerBucketSorter (); Popis nije sortiran = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); Očekivani popis = Arrays.asList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); Popis sortirano = sorter.sort (nesortirano); assertEquals (očekuje se, sortira);

5. Složenost vremena

Dalje, pogledajmo na brzinu složenost izvođenja sortiranja segmenta.

5.1. Najgori scenarij

U našem najgorem scenariju bismo to pronašli svi naši elementi u istoj skupini i obrnutim redoslijedom. Kada se dogodi ovaj slučaj, reduciramo grupnu sortiranje na jednostavnu sortiranje u kojoj se svaki element uspoređuje sa svim ostalim elementima dajući vremensku složenost O (n²).

5.2. Prosječni scenarij slučaja

U našem prosječnom slučaju nalazimo da elementi su relativno ravnomjerno raspoređeni među našim ulaznim segmentima. Budući da svaki od naših koraka zahtijeva samo jednu iteraciju kroz naše ulazne segmente, otkrivamo da se naša sekvenca sortira dovršava u O (n) vremenu.

6. Zaključak

U ovom smo članku vidjeli kako implementirati sortiranje segmenata u Javi. Također smo pogledali vremensku složenost algoritma za sortiranje segmenata.

Kao i uvijek, kod prikazan u ovom članku dostupan je na GitHub-u.