Bucket sorteren in Java

1. Inleiding

In dit artikel gaan we dieper in op de bucket-sorteeralgoritme. We beginnen met een korte stukje theorie, voordat u aan de Java-implementatie gaat werken naast het testen van onze oplossing. Eindelijk zullen we kijk naar de tijdcomplexiteit van het sorteren van emmers.

2. De theorie van het sorteren van emmers

Emmersortering, ook wel bin-sortering genoemd, is een specifiek sorteeralgoritme. Het sorteren werkt door de elementen die we willen sorteren te verdelen in verschillende individueel gesorteerde emmers. Door dit te doen, kunnen we het aantal vergelijkingen tussen de elementen verminderen en de sorteringstijd helpen verkorten.

Laten we het stappen die nodig zijn om een ​​bucket-sortering uit te voeren:

  1. Zet een reeks van onze aanvankelijk lege emmers op
  2. Verdeel onze elementen in hun geschikte emmers
  3. Sorteer elke emmer
  4. Voeg de gesorteerde buckets samen om de volledige lijst opnieuw te maken

3. Java-implementatie

Hoewel dit algoritme niet taalspecifiek is, zullen we de sortering in Java implementeren. Laten we de bovenstaande lijst stap voor stap doorlopen en de code schrijven om een ​​lijst met gehele getallen te sorteren.

3.1. Emmeropstelling

Ten eerste, wij moeten een hash-algoritme bepalen om te beslissen welke van onze elementen in welke bucket worden geplaatst:

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

Met onze hash-methode gedefinieerd, kunnen we nu specificeer het aantal bakken als een vierkantswortel van de invoerlijstgrootte:

final int numberOfBuckets = (int) Math.sqrt (initialList.size ()); Lijst buckets = nieuwe ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (new ArrayList ()); }

Ten slotte hebben we een korte methode nodig om het maximale gehele getal in onze invoerlijst te bepalen:

private int findMax (lijstinvoer) {int m = Integer.MIN_VALUE; for (int i: input) {m = Math.max (i, m); } geef m terug; }

3.2. De elementen verdelen

Nu we onze emmers hebben gedefinieerd, kunnen we distribueer elk element van onze invoerlijst in zijn relevante bucket met behulp van de hash methode:

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

3.3. De individuele bakken sorteren

Met onze emmers gedefinieerd en vol met gehele getallen, laten we een Comparator om ze te sorteren:

Comparator comparator = Comparator.naturalOrder (); for (List bucket: buckets) {bucket.sort (comparator); }

3.4. Onze emmers aaneenschakelen

Ten slotte moeten we onze emmers samenbrengen om de enkele lijst opnieuw te maken. Omdat onze buckets zijn gesorteerd, hoeven we elke bucket maar één keer te doorlopen en de elementen aan een hoofdlijst toe te voegen:

Lijst gesorteerdArray = nieuwe LinkedList (); voor (Lijstemmer: emmers) {gesorteerdArray.addAll (emmer); } terug gesorteerdArray;

4. Onze code testen

Nu onze implementatie is voltooid, laten we een snelle eenheidstest schrijven om te controleren of deze werkt zoals verwacht:

BucketSorter sorter = nieuwe IntegerBucketSorter (); Lijst ongesorteerd = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); Lijst verwacht = Arrays.asList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); Lijst gesorteerd = sorter.sort (ongesorteerd); assertEquals (verwacht, gesorteerd);

5. Tijdscomplexiteit

Laten we vervolgens snel kijken naar de tijdcomplexiteit van het uitvoeren van een bucket-sortering.

5.1. In het slechtste geval

In ons ergste scenario zouden we ontdekken al onze elementen in dezelfde emmer en in omgekeerde volgorde. Wanneer dit geval zich voordoet, verkleinen we onze bucket-sortering tot een eenvoudige sortering waarin elk element wordt vergeleken met elk ander element, wat een tijdcomplexiteit oplevert van O (n²).

5.2. Gemiddeld casusscenario

In ons gemiddelde geval vinden we dat de elementen zijn relatief gelijkmatig verdeeld over onze invoerbakken. Omdat elk van onze stappen slechts één iteratie door onze invoerbakken vereist, merken we dat onze bucket sorteert voltooid in O (n) tijd.

6. Conclusie

In dit artikel hebben we gezien hoe we een bucket-sortering in Java kunnen implementeren. We hebben ook gekeken naar de tijdcomplexiteit van het bucket-sorteeralgoritme.

Zoals altijd is de code die in dit artikel wordt getoond, beschikbaar op GitHub.