Bucket Sort i Java

1. Introduksjon

I denne artikkelen vil vi dykke inn i skuffesorteringsalgoritme. Vi begynner med et raskt litt teori, før du jobber med Java-implementeringen sammen med enhetstesting av løsningen. Til slutt vil vi se på tidskompleksiteten av skuffesortering.

2. Theory of Bucket Sorting

Bøkesortering, noen ganger kjent som søppel sortering, er en spesifikk sorteringsalgoritme. Sorteringen fungerer ved å fordele elementene vi ønsker å sortere i flere individuelt sorterte bøtter. Ved å gjøre dette kan vi redusere antall sammenligninger mellom elementene og bidra til å kutte sorteringstiden.

La oss ta en rask titt på trinn som kreves for å utføre en skuffesortering:

  1. Sett opp en rekke av våre opprinnelig tomme bøtter
  2. Fordel elementene våre i passende skuffer
  3. Sorter hver bøtte
  4. Sett sammen de sorterte bøttene sammen for å gjenskape hele listen

3. Java-implementering

Selv om denne algoritmen ikke er språkspesifikk, implementerer vi typen i Java. La oss gå gjennom listen over trinn for trinn og skrive koden for å sortere en liste over heltall.

3.1. Bøtteoppsett

Først vi trenger å bestemme en hashingalgoritme å bestemme hvilke av elementene våre som blir plassert i hvilken bøtte:

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

Med vår hash-metode definert, kan vi nå angi antall søppel som en kvadratrot av inngangslistestørrelsen:

final int numberOfBuckets = (int) Math.sqrt (initialList.size ()); Liste bøtter = ny ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (new ArrayList ()); }

Til slutt trenger vi en kort metode for å bestemme det maksimale heltallet i inngangslisten vår:

privat int findMax (listeinngang) {int m = Heltall.MIN_VALUE; for (int i: input) {m = Math.max (i, m); } returner m; }

3.2. Distribuere elementene

Nå som vi har definert skuffene våre, kan vi distribuer hvert element i inngangslisten vår i den aktuelle bøtta ved hjelp av hasj metode:

int max = findMax (initialList); for (int i: initialList) {buckets.get (hash (i, max, numberOfBuckets)). legg til (i); } 

3.3. Sortering av de enkelte skuffene

Med skuffene våre definert og fulle av heltall, la oss bruke en Komparator for å sortere dem:

Comparator comparator = Comparator.naturalOrder (); for (List bøtte: bøtter) {bucket.sort (komparator); }

3.4. Sammenkobling av skuffene våre

Til slutt må vi trekke skuffene våre for å gjenskape den eneste listen. Siden skuffene våre er sortert, trenger vi bare å gå gjennom hver bøtte en gang og legge elementene til en hovedliste:

List sortedArray = new LinkedList (); for (List bøtte: bøtter) {sortedArray.addAll (bøtte); } return sortedArray;

4. Testing av koden vår

Når implementeringen er fullført, la oss skrive en rask enhetstest for å sikre at den fungerer som forventet:

BucketSorter sorter = ny IntegerBucketSorter (); Liste usortert = 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 (usortert); assertEquals (forventet, sortert);

5. Tidskompleksitet

Deretter, la oss ta en rask titt på tidskompleksiteten til å utføre en bøtte-sortering.

5.1. I verste fall

I vårt verste fall vil vi finne det alle elementene våre i samme bøtte og i omvendt rekkefølge. Når denne saken oppstår, reduserer vi sorteringen vår til en enkel slags der hvert element sammenlignes med hvert annet element, gir en tidskompleksitet på O (n²).

5.2. Gjennomsnittlig saksscenario

I vårt gjennomsnittlige tilfelle finner vi at elementene er relativt jevnt fordelt mellom våre innsatsbøtter. Siden hvert av trinnene våre bare krever en iterasjon gjennom inngangsbøttene våre, finner vi ut at bøtta vår sorterer fullfører på O (n) tid.

6. Konklusjon

I denne artikkelen så vi hvordan vi implementerer en skuffesortering i Java. Vi så også på tidskompleksiteten til skuffesorteringsalgoritmen.

Som alltid er koden vist i denne artikkelen tilgjengelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found