Bucket Sort i Java

1. Introduktion

I denne artikel dykker vi ned i bucket sorteringsalgoritme. Vi starter med et hurtigt lidt teori, inden du arbejder på Java-implementeringen sammen med enhedstest vores løsning. Endelig skal vi se på tidens kompleksitet af spandesortering.

2. Theory of Bucket Sorting

Bucket sortering, undertiden kendt som bin sortering, er en specifik sorteringsalgoritme. Sorteringen fungerer ved at distribuere de elementer, vi vil sortere, i flere individuelt sorterede spande. Ved at gøre dette kan vi reducere antallet af sammenligninger mellem elementerne og hjælpe med at reducere sorteringstiden.

Lad os tage et hurtigt kig på trin, der kræves for at udføre en skovlsortering:

  1. Opret en matrix af vores oprindeligt tomme spande
  2. Fordel vores elementer i deres passende spande
  3. Sorter hver spand
  4. Sammenkæd de sorterede skovle for at genskabe den fulde liste

3. Java-implementering

Selvom denne algoritme ikke er sprogspecifik, implementerer vi typen i Java. Lad os gå igennem ovenstående liste trin for trin og skrive koden for at sortere en liste over heltal.

3.1. Opsætning af spand

Først vi skal bestemme en hashingalgoritme at afgøre, hvilke af vores elementer der placeres i hvilken spand:

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

Med vores hash-metode defineret kan vi nu Angiv antallet af skraldespande som en kvadratrode af inputlistestørrelsen:

endelig int numberOfBuckets = (int) Math.sqrt (initialList.size ()); Liste spande = nye ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (ny ArrayList ()); }

Endelig har vi brug for en kort metode til at bestemme det maksimale heltal i vores inputliste:

privat int findMax (listeindgang) {int m = Heltal.MIN_VÆRDI; for (int i: input) {m = Math.max (i, m); } returner m; }

3.2. Distribuere elementerne

Nu hvor vi har defineret vores skovle, kan vi distribuer hvert element på vores inputliste i den relevante spand ved hjælp af hash metode:

int max = findMax (initialList); for (int i: initialList) {buckets.get (hash (i, max, numberOfBuckets)). tilføj (i); } 

3.3. Sortering af de enkelte skovle

Med vores skovle defineret og fulde af heltal, lad os bruge en Komparator for at sortere dem:

Comparator comparator = Comparator.naturalOrder (); for (Liste spand: spande) {bucket.sort (komparator); }

3.4. Sammenkædning af vores spande

Endelig er vi nødt til at trække vores spande sammen for at genskabe den enkelte liste. Da vores skovle er sorteret, behøver vi kun at løbe gennem hver skovl en gang og tilføje elementerne til en hovedliste:

List sortedArray = new LinkedList (); for (Liste spand: spande) {sortedArray.addAll (spand); } returner sorteretArray;

4. Test af vores kode

Når vores implementering er gennemført, lad os skrive en hurtig enhedstest for at sikre, at den fungerer som forventet:

BucketSorter sorter = ny IntegerBucketSorter (); Liste usorteret = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); Liste forventet = Arrays.asList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort (usorteret); assertEquals (forventet, sorteret);

5. Tidskompleksitet

Lad os derefter tage et hurtigt kig på tidskompleksiteten ved at udføre en skovlsortering.

5.1. Værste tilfælde

I vores værst tænkelige scenario finder vi det alle vores elementer i samme spand og i omvendt rækkefølge. Når denne sag opstår, reducerer vi vores skovsortering til en simpel slags, hvor hvert element sammenlignes med hvert andet element, hvilket giver en tidskompleksitet på O (n²).

5.2. Gennemsnitlig sagsscenarie

I vores gennemsnitlige tilfælde finder vi, at elementer er relativt jævnt fordelt mellem vores inputspande. Da hvert af vores trin kun kræver en iteration gennem vores inputspande, finder vi ud af, at vores spand er sorteret afsluttes om O (n) tid.

6. Konklusion

I denne artikel så vi, hvordan man implementerer en bucket-sortering i Java. Vi kiggede også på tidskompleksiteten af ​​bucket sorteringsalgoritmen.

Som altid er koden vist i denne artikel tilgængelig på GitHub.