Hogyan lehet megvalósítani az egyesítés rendezését C ++ nyelven példákkal

Mi az egyesítési fajta? A Merge sort egy összehasonlításon alapuló rendezési algoritmus, amely a divide and conquer kategóriába tartozik. Az Egyesítés rendezés egy tömb rendezésére szolgál az osztás és meghódítás stratégia alapján, amelyre ebben a bejegyzésben röviden kitérünk, más fogalmakkal együtt, például algoritmusával és egy példájával. Megvizsgáljuk az egyesítés rendezésének időbeli összetettségét C ++ nyelven is

A következő hivatkozásokkal foglalkozunk ebben a cikkben,

• Oszd meg és hódítsd meg az algoritmust
• Az Egyesítés rendezési algoritmus megértése egy példával
• Pszeudokód az egyesítés rendezéséhez
• Programozás C ++ formátumban a Merge Sort számára
• A Merge Sort időbeli összetettsége

Folytatás ezzel a cikkel az Egyesítés rendezése C ++ nyelven

Divide and Conquer algoritmus

Ha már ismeri a quicksort működését, akkor tisztában lehet az osztani és meghódítani stratégiával. A Divide and Conquer három fő lépést tartalmaz. Ezen lépések megértése érdekében vegyünk fontolóra egy Hello [] tömböt, amelynek „a” kezdő indexe és „n” vége indexe van, így a tömbünket a következő módon írhatjuk meg: Hello [a & hellip..n]

Divide - Az osztás és meghódítás elsődleges lépése vagy elsődleges lépése az, hogy az adott problémát részproblémákra vagy részrészekre osztja. A fogás itt az, hogy az alproblémáknak hasonlóaknak kell lenniük az eredeti problémához és kisebb méretűek. Esetünkben tömbünket két felére osztjuk [a & hellip.m] [m + 1 & hellip..n] m az a és n index közepén fekszik.

Hódítás - Ha végeztünk, problémánkat alproblémákra osztottuk. Rekurzív módon oldjuk meg ezeket az alproblémákat.

Összevonás - Ebben a lépésben megfelelő módon egyesítjük részproblémáink összes megoldását. Más szavakkal, két különböző rendezett tömböt egyesítünk egy rendezett tömb kialakításához. Itt van a rendezett tömb.

Folytatás ezzel a cikkel az Egyesítés rendezése C ++ nyelven

A Merge Sort algoritmus megértése egy példával

Ezen a ponton tudjuk, hogy az egyesítés rendezés milyen megközelítést fog használni. Vegyünk egy példát, és haladjunk át minden lépést a Hello [] -tól rendezetlenül egy rendezett tömbig.
Példa - Helló [10, 3, 7, 1, 15, 14, 9, 22]

sor adatstruktúra java-ban

A fenti képen egy nem rendezett tömböt vettünk figyelembe, és az egyesítés rendezését használtuk a rendezett tömb megszerzéséhez. Most nézzük meg az egyes lépéseket, és értsük meg az egész algoritmust

1. Először egy Hello tömböt vettünk figyelembe [10, 3, 7, 1, 15, 14, 9, 22] ebben a tömbben összesen 8 elem van

2. Amint azt korábban láthattuk, az egyesítés rendezése a divide and conquer megközelítést használja az elemek rendezéséhez. Találtunk m-t, amely a tömb közepén fekszik, és töredékünket elosztottuk a közepétől, ahol m = (a - n) / 2 'a' a bal oldali elem indexe, n pedig tömbünk jobb szélső elemének indexe .

3. Az első osztás után 2 részünk van, amelyek mindegyike 4 elemből áll. Nézzük az első felet [10, 3, 7, 1].

4. A [10, 3, 7, 1] 2 részre osztjuk [10, 3] és [7, 1]. Ezt követően tovább osztjuk őket [10], [3], [7], [1]. További felosztás nem lehetséges, mivel nem tudjuk kiszámítani az m-t. az egyetlen elemet tartalmazó lista mindig rendezettnek tekintendő.

5. Hogyan történik az egyesülés? Találjuk ki. Először [10] és [3] összehasonlítjuk és összevonjuk növekvő sorrendben [3, 10] ugyanúgy, ahogy megkapjuk [1, 7]

írja be a konverziót c ++ -ban

6. Ezt követően összehasonlítjuk a [3, 10] és [1, 7]. Miután összehasonlítottuk, növekvő sorrendben egyesítjük őket, és megkapjuk [1, 3, 7, 10].

7. [15, 14, 9, 2] szintén fel van osztva és hasonló módon kombinálva [9, 14, 15, 22] képződik.

8. Az utolsó lépésben összehasonlítjuk és kombináljuk a [15, 14, 9, 2] [9, 14, 15, 22], hogy megkapjuk a rendezett tömbötazaz [1, 3, 7, 9, 10, 14, 15, 22].

hogyan lehet kilépni egy java programból

Folytatás ezzel a cikkel az Egyesítés rendezése C ++ nyelven

Pszeudokód az egyesítés rendezéséhez

Kezdje, ha marad
A mergeSort () függvény rekurzívan hívja magát tömbünk felosztására, amíg egyetlen elemmé nem válik, és az egyesítés () függvényt a rendezett tömbök egyesítésére használják.
  Folytatás ezzel a cikkel az Egyesítés rendezése C ++ nyelven
 A rendezési program egyesítése C ++ nyelven 
#include #include #include névtér használatával std void merge (int a [], int Firstindex, int m, int Lastindex) // összevonja a létrehozott altömböket, míg a divízió void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexméret int Helló [méret], i cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hello [i] mergeSort (Hello, 0, méret - 1) cout<<'The Sorted List isn' for(i=0 i
 Kimenet- 
Folytatás ezzel a cikkel az Egyesítés rendezése C ++ nyelven
 Idő komplexitás 
Az idő bonyolultsága fontos szempont, amelyet figyelembe kell venni, amikor algoritmusokról beszélünk. Az egyesítés rendezése nagy időbonyolultságúnak tekinthető a többi rendezési algoritmushoz képest.
Legrosszabb futási idő - O (n log n) 
Legjobb eset futási idő - O (n log n) 
Átlagos futási idő - O (n log n)
Ezzel véget értünk ennek a Merge Sort in C ++ cikknek. Ha többet szeretne megtudni, nézze meg a   Edureka, egy megbízható online tanulási társaság. Az Edureka Java J2EE és SOA képzési és tanúsítási tanfolyamát arra tervezték, hogy mind az alapvető, mind a fejlett Java koncepciókra kiképezzen különféle Java keretrendszereket, például a Hibernate & Spring.
 Van egy kérdésünk? Kérjük, említse meg a blog megjegyzés rovatában, és a lehető leghamarabb kapcsolatba lépünk Önnel.