streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megnézzük a Merge Sort algoritmus és annak megvalósítása Java-ban.

A rendezés egyesítése az egyik leghatékonyabb rendezési technika, és az „oszd meg és hódítsd” paradigmán alapul.

2. Az algoritmus

A Merge sort egy „oszd meg és meghódítsd” algoritmus, amelyben a problémát először részproblémákra osztjuk. Amikor az alproblémák megoldása készen áll, ezeket egyesítjük, hogy megkapjuk a probléma végleges megoldását.

Ez az egyik olyan algoritmus, amely könnyen megvalósítható rekurzióval, mivel a főprobléma helyett az alproblémákkal foglalkozunk.

Az algoritmus a következő kétlépcsős folyamatként írható le:

• Osztás: Ebben a lépésben a bemeneti tömböt két részre osztjuk, a pivot a tömb középpontja. Ezt a lépést rekurzívan hajtják végre az összes fél tömb esetében, amíg nincs több fél tömb, amelyet fel kellene osztani.
• Hódítás: Ebben a lépésben válogatjuk és egyesítjük az osztott tömböket alulról felfelé és kapja meg a rendezett tömböt.

Az alábbi ábra bemutatja a teljes egyesítési rendezési folyamatot egy példa tömb ({10, 6, 8, 5, 7, 3, 4}) számára.

Ha jobban megnézzük a diagramot, láthatjuk, hogy a tömb rekurzívan két félre oszlik, amíg a méret 1. nem lesz. Miután a méret 1 lesz, az egyesítési folyamatok működésbe lépnek, és válogatás közben megkezdik a tömbök egyesítését:

3. Végrehajtás

A megvalósításhoz írunk egy egyesítésSort függvény, amely beveszi a bemeneti tömböt és annak hosszát mint paramétereket. Ez rekurzív függvény lesz, ezért szükségünk van az alapra és a rekurzív feltételekre.

Az alapfeltétel ellenőrzi, hogy a tömb hossza 1, és csak visszatér. A többi esetben a rekurzív hívás végrehajtásra kerül.

A rekurzív esethez megkapjuk a középső indexet, és létrehozunk két ideiglenes tömböt l [] és r []. A egyesítésSort A függvényt ekkor rekurzívan hívjuk meg mindkét altömbnél:

public static void mergeSort (int [] a, int n) {if (n <2) {return; } int közepe = n / 2; int [] l = új int [közepes]; int [] r = új int [n - közepe]; mert (int i = 0; i <középső; i ++) {l [i] = a [i]; } for (int i = közép; i <n; i ++) {r [i - közép] = a [i]; } mergeSort (l, közepe); egyesítésSort (r, n - közepe); egyesülés (a, l, r, közepe, n - közepe); }

Ezután felhívjuk a összeolvad függvény, amely beveszi a bemenetet és az al tömböket, valamint a kezdő és a vég indexeket mindkét al tömbhöz.

A összeolvad függvény egyesével összehasonlítja mindkét altömb elemeit, és a kisebb elemet a bemeneti tömbbe helyezi.

Amikor az egyik résztömb végére érünk, a másik tömb többi elemét átmásoljuk a bemeneti tömbbe, ezáltal megkapjuk a végső rendezett tömböt:

public static void egyesülés (int [] a, int [] l, int [] r, int bal, int jobb) {int i = 0, j = 0, k = 0; míg (i <bal && j <jobb) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } else {a [k ++] = r [j ++]; }} while (i <balra) {a [k ++] = l [i ++]; } while (j <jobbra) {a [k ++] = r [j ++]; }} 

A program egységtesztje:

@Test public void pozitívTest () {int [] tényleges = {5, 1, 6, 2, 3, 4}; int [] várható = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (tényleges, tényleges.hossz); assertArrayEquals (várható, tényleges); }

4. Komplexitás

Mivel az egyesítés rendezése rekurzív algoritmus, az idő bonyolultsága a következő rekurzív összefüggésként fejezhető ki:

T (n) = 2T (n / 2) + O (n)

2T (n / 2) megfelel az altömbök rendezéséhez szükséges időnek és Tovább) ideje összevonni a teljes tömböt.

Megoldás után elérkezik az idő bonyolultsága O (nLogn).

Ez a legrosszabb, átlagos és legjobb esetben is igaz, mivel mindig ketté fogja osztani a tömböt, majd egyesül.

Az algoritmus térbeli összetettsége az Tovább) mivel minden rekurzív hívásnál ideiglenes tömböket hozunk létre.

5. Következtetés

Ebben a gyors oktatóanyagban láthattuk az egyesítés rendezésének algoritmusának működését és azt, hogy miként tudjuk megvalósítani a Java-ban.

A teljes munkakód elérhető a GitHubon.