streamalism.org

1. Bemutatkozás

Ebben a cikkben elmélyülünk a vödör rendezési algoritmus. Kezdjük egy gyorssal elmélet, mielőtt a Java megvalósításán dolgozna a megoldásunk tesztelésével. Végül megtesszük nézd meg az idő összetettségét vödör válogatás.

2. A vödörrendezés elmélete

A vödrös válogatás, amelyet néha kuka szerinti válogatásnak is neveznek, egy sajátos rendezési algoritmus. A rendezés úgy működik, hogy az elemeket, amelyeket rendezni szeretnénk, több egyenként rendezett vödörbe osztja szét. Ezzel csökkenthetjük az elemek összehasonlításának számát, és csökkenthetjük a rendezési időt.

Vessünk egy gyors pillantást a a vödörrendezés elvégzéséhez szükséges lépések:

1. Állítson be egy tömböt az eredetileg üres vödrökből
2. Ossza szét elemeinket a megfelelő vödrökbe
3. Rendezzen minden vödröt
4. Összekapcsolja a válogatott vödröket a teljes lista létrehozásához

3. Java implementáció

Bár ez az algoritmus nem nyelvspecifikus, a rendezést a Java-ban valósítjuk meg. Menjünk át lépésről lépésre a fenti listán, és írjuk be a kódot az egész számok rendezéséhez.

3.1. Vödör beállítása

Először mi meg kell határoznia egy kivonatoló algoritmust hogy eldöntsük, melyik elemünk melyik vödörbe kerül:

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

A hash-módszerünk definiálásával most megtehetjük adja meg a tárolók számát a bemeneti lista méretének négyzetgyökeként:

végső int számOfBuckets = (int) Math.sqrt (initialList.size ()); Lista vödrök = new ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (új ArrayList ()); }

Végül egy rövid módszerre van szükségünk a maximális egész szám meghatározásához a bemeneti listánkban:

privát int findMax (Lista bemenet) {int m = Egész.MIN_VALUE; for (int i: input) {m = Math.max (i, m); } visszatérés m; }

3.2. Az elemek terjesztése

Most, hogy meghatároztuk a vödröket, megtehetjük terjessze a bemeneti listánk minden elemét a megfelelő csoportba a hash módszer:

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

3.3. Az egyes vödrök rendezése

Meghatározott és egész számokkal rendelkező vödrökkel használjuk a Összehasonlító válogatni őket:

Összehasonlító összehasonlító = Comparator.naturalOrder (); for (Lista vödör: vödrök) {vödör.sort (összehasonlító); }

3.4. Összevissza vödrünket

Végül össze kell szednünk a vödröket az egységes lista újrateremtéséhez. Mivel a vödrök rendezve vannak, csak egyszer kell végignéznünk az egyes vödröket, és az elemeket hozzá kell fűznünk egy fő listához:

List sortedArray = new LinkedList (); for (Lista vödör: vödrök) {sortedArray.addAll (vödör); } return sortedArray;

4. Kódunk tesztelése

A megvalósításunk befejezésével írjunk egy gyors egységtesztet, hogy megbizonyosodjunk arról, hogy az a várt módon működik:

BucketSorter válogató = new IntegerBucketSorter (); Lista nem rendezve = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); Várható lista = tömbök. AsList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); Lista rendezve = válogató.sort (rendezetlen); assertEquals (várható, rendezve);

5. Az idő komplexitása

Ezután vessünk egy gyors pillantást a vödörfajta végrehajtásának időbeli összetettségére.

5.1. A legrosszabb esetben

Legrosszabb esetünkben megtalálnánk minden elemünk ugyanabban a vödörben és fordított sorrendben. Amikor ez az eset bekövetkezik, a sorrendet egyszerű sorrendre redukáljuk, amelyben minden elemet összehasonlítunk minden más elemmel, O (n2) időbeli komplexitását eredményezve.

5.2. Átlagos eset forgatókönyv

Átlagos esetünkben azt tapasztaljuk, hogy a az elemek viszonylag egyenletesen oszlanak meg a bemeneti vödrök között. Mivel mindegyik lépésünk csak egy iterációt igényel a bemeneti vázlatainkon keresztül, azt tapasztaljuk, hogy a vödrünk rendeződik O (n) időben befejeződik.

6. Következtetés

Ebben a cikkben azt láttuk, hogyan lehet egy vödör rendezést megvalósítani a Java-ban. Megvizsgáltuk a vödrös rendezési algoritmus időbeli összetettségét is.

Mint mindig, az ebben a cikkben bemutatott kód elérhető a GitHubon.